PEG Judge - COCI09 #2

COCI 2009/2010, Contest #2

Task POSLOZI

"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!

Input

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.

Output

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.