You are playing Duck Duck Patapim in a park with ~n~ benches connected by ~m~ walkways.

You start at bench ~s~ and want to shout "GO!" while standing at bench ~t~. Each walkway connects two benches in both directions, and crossing one walkway counts as one move.

Some benches are special. You may visit benches and cross walkways multiple times. A route is valid only if, when you shout "GO!", both of the following are true:

1. You are currently at bench ~t~.
2. At some point along your route, including the starting and ending benches, you have visited at least one special bench.

For example, if ~s = t~ but bench ~s~ is not special, the answer is not ~0~: staying still does not visit a special bench. You must move away, visit a special bench, and then return to ~t~.

What is the minimum number of moves needed? If it is impossible, print ~-1~.

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n \leq 10^5,\ 0 \leq m \leq 2 \times 10^5)~: the number of benches and walkways.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~, where each ~a_i~ is ~0~ or ~1~. If ~a_i = 1~, bench ~i~ is a special bench; otherwise it is a normal bench.

Each of the next ~m~ lines contains two integers ~u~ and ~v~ ~(1 \leq u, v \leq n,\ u \neq v)~, meaning there is a walkway between benches ~u~ and ~v~. No walkway appears more than once.

The last line contains two integers ~s~ and ~t~ ~(1 \leq s, t \leq n)~: your starting bench and the bench where you want to shout "GO!".

Output

Print one integer: the minimum number of moves in a valid route, or ~-1~ if no valid route exists.

Example

Input 1

3 2
0 1 0
1 2
2 3
1 1

Output 1

2

You start and finish at bench ~1~, but bench ~1~ is not special. A shortest valid route is ~1 \to 2 \to 1~: you visit the special bench ~2~, then return to bench ~1~. Simply staying at bench ~1~ is invalid, even though ~s = t~.

Input 2

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

Output 2

4

A shortest valid route is ~1 \to 2 \to 3 \to 4 \to 5~. You visit the special bench ~2~ and finish at bench ~5~ after four moves.

Input 3

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

Output 3

-1

Benches ~1~ and ~2~ are disconnected from benches ~3~ and ~4~. Since you start at bench ~1~, you can never reach the component containing the only special bench and ~t = 4~.