编程题：A*算法/双向搜索

“Arrange”是一款全球流行的Flash游戏。在“Arrange”中，玩家被赋予一个数字1到N的排列和一个允许交换的列表。然后，他必须执行一系列交换，将初始排列转换回有序序列1、2、3、4、5…N

为了打破高分榜，你需要尽可能少地进行掉期交易。你不能这么做，但你可以编写一个程序来为你做到这一点！




### 输入格式:
第一行输入包含两个整数N（1≤N≤12），初始序列的长度和M（1≤M≤N*（N–1）/2）允许互换的数量。

第二行输入包含数字1到N的排列。

接下来的M行包含允许互换的描述。如果该行包含数字A和B，则允许将A号与B号交换。输入永远不会包含两个相同的交换。

注：试验数据应确保溶液（不一定是唯一的）始终存在

### 输出格式:
在输入的第一行中，打印交换的最小数量X。

在接下来的X行中，按顺序打印所需的掉期。在每行打印所执行交换的索引。随着掉期在输入中的出现，其编号也越来越多，从1开始

### 输入样例1:
in
2 1
2 1
1 2


### 输出样例1:
out
1
1


### 输入样例2:
in
3 2
2 1 3
1 3
2 3


### 输出样例2:
out
3
2
1
2


### 输入样例3:
in
5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5


### 输出样例3:
out
0









答案：若无答案欢迎评论