"Arrange" is a planetary popular Flash game. In "Arrange" the player is given a permutation of numbers ~1~ to ~N~ and a list of allowed swaps. He then has to perform a sequence of swaps that transforms the initial permutation back to the ordered sequence ~1, 2, \dots, N~.

In order to break the high score list, you need to perform the minimal amount of swaps possible. You can't do that, but you can write a program that does it for you!

Input Specification

The first line of input contains two integers, ~N~ ~(1 \le N \le 12)~, the length of the initial sequence and ~M~ ~(1 \le M \le \frac{N \times (N-1)}{2})~ number of allowed swaps.

The second line of input contains a permutation of number ~1~ to ~N~. The next ~M~ lines contain descriptions of allowed swaps. If the line contains numbers ~A~ and ~B~ you are allowed to swap the ~A^\text{th}~ number with the ~B^\text{th}~ number. The input will never contain two identical swaps.

Note: the test data shall be such that the solution, not necessarily unique, will always exist.

Output Specification

In the first line of input print the minimal number of swaps, ~X~.

In the next ~X~ lines print the required swaps, in order. In each line print the index of the swap performed. Swaps are numbered increasingly as they appear in the input, starting from ~1~.

Sample Input 1

2 1
2 1
1 2

Sample Output 1

1
1

Sample Input 2

3 2
2 1 3
1 3
2 3

Sample Output 2

3
2
1
2

Sample Input 3

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

Sample Output 3

0