Coloured Bridges A (1/2/4 Points)

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

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

0

4 2
1 2 1 3
1 2
3 4

1

3 0
0 1 2

-1

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

1