← 返回题目
题库练习 「COCI 2009.11」POSLOZI
← 上一题 下一题 →

A6388 | 「COCI 2009.11」POSLOZI

时间限制1500ms
内存限制32MB
通过 / 提交0/0

题目描述

**译自 [COCI 2009.11](http://hsin.hr/coci/archive/2009_2010/) T5.** ***[POSLOZI](http://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)***

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

输入格式

第一行两个整数 $N,$ $M$。
第二行 $N$ 个整数，表示排列。
接下来 $M$ 行，第 $i$ 行有两个整数，表示第 $i$ 种修改方式。

输出格式

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

输入输出样例

输入 #1
2 1
2 1
1 2
输出 #1
1
1
输入 #2
3 2
2 1 3
1 3
2 3
输出 #2
3
2
1
2
输入 #3
5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5
输出 #3
0
C++ 编辑器
输入
输出