"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