In order to cool down, Iino devised a game she calls Whack-an-Ishigami.

In this game, she has ~N~ Ishigami figures lined up in a row, some up and some down. There are also ~M~ connections ~(a_i, b_i)~, the ~i~-th of which causes the ~b_i~-th Ishigami's state to flip when the ~a_i~-th Ishigami's state is flipped. Note that this can cause a chain reaction. If the reactions cause an infinite sequence of flipping, Iino has to reset the game.

In one move, you can whack an Ishigami, flipping its state from up to down or vice versa (this may also cause others to flip). The goal of the game is to get all the Ishigamis down. However, Iino is having trouble, so she turns to you for help. What is the minimum number of moves you need to flip all Ishigamis down?

Constraints

~1 \le N, M \le 10^6~

~k_i \in \{0, 1\}~

~1 \le a_i, b_i \le N~

~a_i \ne b_i~

There do not exist two integers ~1 \le i < j \le N~ such that ~a_i = a_j~ and ~b_i = b_j~.

Subtask 1 [20%]

~a_i < b_i~

Subtask 2 [20%]

~1 \le N, M \le 5 \times 10^3~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains ~2~ integers ~N~ and ~M~.

The next line contains ~N~ space-separated integers ~k_i~. If ~k_i = 1~ then the ~i~-th Ishigami is up. Otherwise, it is down.

The next ~M~ lines each contain ~2~ integers ~a_i~ and ~b_i~.

Output Specification

Output one integer, the minimum number of moves required. If it is impossible to flip all the Ishigamis down without having to reset the game, output -1.

Sample Input 1

3 3
0 1 1
3 1
1 2
3 2

Sample Output 1

2

Explanation for Sample 1

First, Iino whacks the first Ishigami, flipping the state of the first and second Ishigamis once. The states are now 1 0 1. Then she whacks the third one, flipping the state of the first and third Ishigamis once and the state of the second Ishigami twice. The states are now 0 0 0, and all the Ishigamis are down.

Sample Input 2

2 2
1 1
1 2
2 1

Sample Output 2

-1