W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
There are monkeys on a tree. They are numbered from to . The monkey number clutches a branch by its tail. Remaining monkeys either are held by other monkeys, hold on to other monkeys or both. Each monkey can use two hands and can hold at most one other monkey in each hand (gripping its tail). Starting from the moment , at each second one monkey releases its grip of one hand. This may cause some monkeys fall down onto the ground, where they can continue releasing their grips (the time of falling is negligibly small).
Write a program which:
The first line of the standard input consists of two positive integers and , , . The number denotes the number of monkeys, and the number denotes the time (in seconds) we observe the monkeys. Next lines contains the description of the initial situation. In the -st line () there are two integers denoting the numbers of monkeys that are hold by the monkey number . The former is the number of the monkey that is hold by the left hand, and the latter - by the right hand. The number denotes that the monkey's hand is free. The following lines denote the result of the observation of the monkeys. In the -th of those lines () there are two integers. The former is the number of the monkey, and the latter is the number of its hand (1 - left, 2 - right) the monkey releases its grip of, in the moment .
Your program should write to the standard output exactly integers, one per line. The number of the -th line should denote the moment the -th monkey fell down onto the ground, or should be equal if the monkey has not fallen down onto the ground during the observation.
For the input data:
3 2 -1 3 3 -1 1 2 1 2 3 1
the correct result is:
-1 1 1
Task author: Andrzej Gasienica-Samek.