Lycanthropy

Time limit5sMemory limit1024 MB

Summary

At each neuron the wolf essence may block up to k outgoing synapses so that a signal never reaches neuron n, in an interactive game on a DAG.

Level: Medium6 of 10
Topics: Graph, Greedy, BFS
Solved: No attempts yet

Input and interaction

Jacob is a werewolf who can turn into a wolf. Right now he is in human form and wants to change into a wolf. But his wolf essence is tired of frequent transformations back and forth, and it tries to resist the change.

To transform into a wolf, Jacob's brain sends a signal into his nervous system. The signal travels down the nervous system, from the brain toward the heart. The nervous system has $n$ neurons and $m$ synapses. The brain generates the signal in the first neuron, and it then propagates to the heart (neuron number $n$ ). Each synapse can carry a signal from neuron $a_i$ to neuron $b_i$ ( $a_i < b_i$ ). When a signal reaches a neuron, it must continue along some synapse. If there is no synapse the signal can take, it fades and no transformation happens. If the signal reaches the heart, the transformation begins.

The wolf essence wants to stop Jacob from starting the transformation. Each time a signal reaches a neuron, the wolf essence can temporarily destabilize at most $k$ synapses. A destabilized synapse cannot carry the signal until the signal leaves the neuron it is in. After the signal leaves, the wolf essence can destabilize synapses again (possibly different ones), and this repeats until the signal fades or the transformation begins. Synapses destabilized earlier recover.

Help the wolf essence make Jacob's transformation fail.

This is an interactive problem.

Hint

Your program must flush the output after every output operation:

Pascal: flush(output);
C/C++: fflush(stdout);
Java: System.out.flush();
Python: sys.stdout.flush();

Also, end every output line with a newline character.

Examples3

Example 1
Input
```
4 4 2
1 2
1 3
2 4
3 4
-1
```
Expected output
```
2 1 2
```
Example 2
Input
```
4 4 2
1 2
1 3
2 4
3 4
2
-1
```
Expected output
```
0
1 3
```
Example 3
Input
```
2 3 2
1 2
1 2
1 2
```
Expected output
```
NO
```