DMOPC '21 Contest 7 P3 - Whack-an-Ishigami

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 (ai,bi), the i-th of which causes the bi-th Ishigami's state to flip when the ai-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

1N,M106

ki{0,1}

1ai,biN

aibi

There do not exist two integers 1i<jN such that ai=aj and bi=bj.

Subtask 1 [20%]

ai<bi

Subtask 2 [20%]

1N,M5×103

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 ki. If ki=1 then the i-th Ishigami is up. Otherwise, it is down.

The next M lines each contain 2 integers ai and bi.

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

Copy
3 3
0 1 1
3 1
1 2
3 2

Sample Output 1

Copy
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

Copy
2 2
1 1
1 2
2 1

Sample Output 2

Copy
-1

Comments

There are no comments at the moment.