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

View as PDF

Submit solution

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

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 (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?


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


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



  • 0
    John  commented on April 22, 2022, 1:41 p.m.

    Poor Ishigami