#1004. [COCI2009-2010#2] POSLOZI

[COCI2009-2010#2] POSLOZI

题目背景

给出一个 1 ~ N 的某种排列。有 M 种允许的修改方式,保证修改方式不重复,每种方式用 L, R 来表示,意为你可以将下标为 L 的数与下标为 R 的数交换。你可以修改该排列若干次。请给出一种修改次数最少的方案,使原排列变为 1, 2, 3, ……, N。如果有多种方案,输出任意一组即可。如果不存在这样的方案,输出 -1

输入格式

第一行两个整数 N, M。

第二行 N 个整数,表示排列。

接下来 M 行,第 i 行有两个整数,表示第 i 种修改方式。

输出格式

首行一个整数 ope_cnt,表示最少的修改次数。

如果 ope_cnt > 0,则接下来 ope_cnt 行,每行一个整数 i,表示进行第 i 种修改。

样例 #1

样例输入 #1

2 1
2 1
1 2

样例输出 #1

1
1

样例 #2

样例输入 #2

3 2
2 1 3
1 3
2 3

样例输出 #2

3
2
1
2

样例 #3

样例输入 #3

5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5

样例输出 #3

0

数据范围

40%的数据:1 <= N <= 7

100%的数据:1 <= N <= 12,1 <= M <= N(N-1)/2