# 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$.

Sample Input 1 | Sample Output 1 |
---|---|

2 1 2 1 1 2 |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

3 2 2 1 3 1 3 2 3 |
3 |

Sample Input 3 | Sample Output 3 |
---|---|

5 5 1 2 3 4 5 1 5 2 5 1 4 1 2 3 5 |
0 |