## Editorial for DMOPC '21 Contest 7 P3 - Whack-an-Ishigami

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

## Subtask 1

Since the graph is a DAG, we never have cycles that would cause us to lose. We maintain a boolean array, initially empty, indicating the parity of the number of times each node has been flipped. Then we process nodes in order, and flip if the flip parity differs from the initial state of the node.## Subtask 2

We can repeat the following process: use BFS/DFS to determine which node to flip. If node is reachable from , it is optimal to flip instead of (similar to Subtask 1). If during the BFS of we find any sort of cycle, and is up at the beginning, output`-1`

. Once we decide what node to flip, we can flip any one of them, and use BFS to update the counts.
Make sure to keep a visited array at each step to avoid degrading into . Furthermore, note that we only need to perform the previous step at most times.
## Comments