#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