Рабочее место участника

“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,\ 3,\ 4,\ 5,\ …,\ 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!

The first line of input contains two integers, `N` (`1\ ≤\ N\ ≤\ 12`), the length of the initial sequence and `M` (`1\ ≤\ M\ ≤\ N*(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`-th number with the `B`-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.

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.

2 1
2 1
1 2

1
1

3 2
2 1 3
1 3
2 3

3
2
1
2

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

0