“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, \ldots , N$.

In order to break the high score list, you need to perform the minimum 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$ ($2 \le N \le 11$), the length of the initial sequence and $M$ ($1 \le M \le N(N – 1) / 2$), the number of allowed swaps.

The second line of input contains a permutation of the numbers $1$ to $N$.

The next $M$ lines contain descriptions of allowed swaps. Each such line contains two distinct numbers $1 \le A < B \le N$, indicating that you are allowed to swap the $A$-th number in the sequence with the $B$-th number. The input never contains two identical swaps.

You may assume that the input is such that a solution exists.

-----Output-----
Output the minimum possible number of swaps to transform the permutation to $1, 2, \ldots , N$.

-----Examples-----
Sample Input 1:
2 1
2 1
1 2
Sample Output 1:
1

Sample Input 2:
3 2
2 1 3
1 3
2 3
Sample Output 2:
3

Source: kattis | Difficulty: HARD


Solutions: