Problem D
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, \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$.

2 1
2 1
1 2

1

3 2
2 1 3
1 3
2 3

3

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

0