#P2361. [Coci2009]POSLOZI ]数列整合

    ID: 1404 传统题 1000ms 128MiB 尝试: 49 已通过: 17 难度: 9 上传者: 标签>CF2600提高+/省选-IDA*可采纳估价函数估价下界剪枝Dijkstra置换循环分解奇偶性分析状态编码状态去重搜索顺序优化路径恢复预计算转移

[Coci2009]POSLOZI ]数列整合

[COCI2009-2010#2] POSLOZI

题目描述

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

评测数据保证至少存在一种合法排序方案。操作按输入顺序从 1 开始编号。

输入格式

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

输出格式

首行一个整数 ope_cnt\mathit{ope\_cnt},表示最少的修改次数。 接下来 ope_cnt\mathit{ope\_cnt} 行,每行一个整数,表示本步执行的操作编号。

样例 #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