“Arrange” 是一款风靡全球的 Flash 游戏。在 “Arrange” 中，玩家会得到一个由数字 $1$ 到 $N$ 组成的排列，以及一系列允许的交换操作。玩家需要执行一系列交换，将初始排列恢复为升序序列 $1, 2, 3, 4, 5 \dots N$。

为了打破最高分记录，你需要用尽可能最少的交换次数来完成。你可能无法手动做到这一点，但你可以写一个程序来帮你完成！

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 12$)，表示初始序列的长度，以及 $M$ ($1 \le M \le N \times (N - 1) / 2$)，表示允许的交换次数。

第二行包含一个数字 $1$ 到 $N$ 的排列。

接下来的 $M$ 行包含允许的交换的描述。如果某一行包含数字 $A$ 和 $B$，则表示你被允许交换第 $A$ 个数和第 $B$ 个数。输入中永远不会包含两个相同的交换。

注意：测试数据保证一定存在解（解不一定唯一）。

输出格式

第一行输出最少交换次数 $X$。

接下来的 $X$ 行按顺序输出所需的交换。每行输出所执行交换的索引。交换的编号按照它们在输入中出现的顺序从 $1$ 开始递增。

样例

输入样例 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