Problem Statement

Warning: This problem is not necessarily easy, this is the easier version of this problem.

You are given an undirected graph with ~n~ vertices (labelled ~1~ through ~n~) and ~m~ edges. Additionally, each vertex has a colour, which is given as a number between ~0~ and ~n~. Between any two vertices of the same colour you may build a bridge (edge) but only if they are not colour ~0~.

Building bridges is expensive so you do not want to build many. You want to get from vertex ~1~ to ~n~ by traversing at little edges as possible, determine the way which cost the least number of bridges.

Determine the minimum number of bridges needed to get from vertex ~1~ to ~n~ in the minimum possible time. If it is not possible to make such a path, output ~-1~.

Input Format

Your first line will contain two integers ~n~ and ~m~ respectively. Your next line will contain ~n~ integers, representing the colours of the ~n~ nodes given in order of the nodes from ~1~ to ~n~. Your next ~m~ lines will contain two integers each, ~u~ and ~v~, meaning there is an edge between node ~u~ and node ~v~.

Output Format

Output a single integer representing the minimum number of bridges needed to get from vertex ~1~ to ~n~ in the minimum possible time.

Constraints

Subtask 1 - 25%:

• ~1 \leq n, m \leq 10^3~

Subtask 2 - 25%:

• ~1 \leq n \leq 10^3~
• ~1 \leq m \leq 10^5~

Subtask 3 - 50%:

• ~1 \leq n, m \leq 10^5~

Sample Cases

Input 1

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

Output 1

0

Input 2

4 2
1 2 1 3
1 2
3 4

Output 2

1

Input 3

3 0
0 1 2

Output 3

-1

Input 4

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

Output 4

1