ml2 | Glassworks

Giorgio and Edoardo are planning to go on a tour of Venice, and they are particularly interested in Murano’s famous colored Venetian glass.

There are $N$ shops which sell glasswares and they are numbered from $0$ to $N − 1$, the $i$-th shop sells only pieces of color $C_i$. Giorgio and Edoardo are interested in visiting some shop and buying some glasswares, they will be happy if they have bought glasswares of at least $3$ different colors.

The fastest (and the only one) way to travel in Murano is by gondola, in particular there are $M$ gondolas, each gondola can carry Giorgio and Edoardo from shop $A_i$ to $B_i$ and viceversa. However, gondolas are not free and each trip requires a ticket (each ticket is valid for one trip only, so taking the same gondola twice requires two tickets).

Giorgio and Edoardo can start and finish the tour in any shop, help them find the minimum number of tickets required to buy at least $3$ glasswares of different colors, or tell that they can’t.

Input data

The first line contains the integers $N$ and $M$, the number of shops and the number of available gondolas. The second line contains $N$ integers, $C_i$ for $i$ = $0 \dots N − 1$.

The following $M$ lines contain $2$ integers $A_i$ and $B_i$ each, meaning that a gondola can travel between shops $A_i$ and $B_i$.

Output data

You need to write a single line with an integer: the minimum number of tickets Giorgio and Edoardo need or $−1$ if they can’t visit shops with glasswares of $3$ different colors.

Constraints and clarifications

• $2 \leq N \leq 500 \ 000$;
• $1 \leq M \leq 500 \ 000$;
• $0 \leq C_i \leq N - 1$;
• $0 \leq A_i, B_i \leq N - 1$, $A_i \neq B_i$;

Example 1

stdin

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

stdout

3

Explanation

In the first sample case it is possible to start the tour in shop $4$, go to shop $2$, then go to shop $5$ and end the tour in shop $1$.

Example 2

stdin

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

stdout

-1

Explanation

In the second sample case it isn’t possible to plan a tour that passes by shops which have glass of $3$ different colors.