#P5183. [COCI2009-2010#2] POSLOZI

[COCI2009-2010#2] POSLOZI

题目背景

译自 COCI 2009.11 T5「POSLOZI

给一个长度为 NN 的排列 (1N12)(1\le N\le 12)。有 MM 种允许的修改方式 (1MN×(N1)2)(1\le M\le \frac{N\times (N-1)}{2}),保证修改方式不重复,每种方式用 L,L, RR 来表示,意为你可以将下标为 LL 的数与下标为 RR 的数交换。你可以修改该排列若干次,请给出一种修改方案,使原排列变为 1,1, 2,2, 3,3, ,\ldots, NN。如果有多种方案,输出修改次数最少的方案。如果还有多种方案,输出任意一组即可。

输入格式

第一行两个整数 N,N, MM
第二行 NN 个整数,表示排列。
接下来 MM 行,第 ii 行有两个整数,表示第 ii 种修改方式。

输出格式

首行一个整数 ope_cnt\mathit{ope\_cnt},表示最少的修改次数。
接下来 ope_cnt\mathit{ope\_cnt} 行,每行一个整数,表示进行第 ii 种修改。

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