There are $N$ people in Shirogane's class, each with a coloured hat of colour $c_i$. Shirogane is person number $1$, and Kaguya is person $N$. People with the same colour of hat get to be in the same group, so naturally Shirogane wants to ensure that him and Kaguya end up in the same group.

It seems that there are $M$ pairs of people willing to trade hats. What is the minimum number of trades Shirogane must perform to ensure he and Kaguya end up in the same group?

Constraints

$2\le N\le {10}^6$

$1\le M\le {10}^6$

$1\le c_i\le N$

Each unordered pair in the input is listed only once.

Subtask 1 [30%]

$2\le N\le 5\times {10}^3$

$1\le M\le 5\times {10}^3$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains two integers, $N$ and $M$.

The next line contains $N$ integers, the $i$th of which is $c_i$.

The next $M$ lines contain two integers each, a pair of people that are willing to swap.

Output Specification

If it is impossible to put Shirogane and Kaguya in the same group, output $-1$.

Otherwise, output the minimum number of swaps required such that Shirogane and Kaguya end up in the same group.

Sample Input 1

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

Sample Output 1

2

Explanation for Sample 1

By performing the swap $(1,2)$ and the swap $(3,4)$, Kaguya and Shirogane end up with the same hat colour.

Sample Input 2

2 1
1 2
1 2

Sample Output 2

-1