P8059 [POI 2003] Monkeys

There are $n$ monkeys on a tree. They are numbered from $1$ to $n$. Monkey $1$ is holding onto a branch with its tail. Each of the remaining monkeys is either hooked by other monkeys or is hooking other monkeys with its hands. Each monkey can use two hands to hook other monkeys, and each hand can hook at most one monkey. Starting from time $0$, every second one monkey lets go with one of its hands. This may cause some monkeys to fall to the ground. We want to know the time when each monkey falls to the ground (the monkeys fall so fast that the falling time can be ignored).

The first line contains two integers $n$ and $m$. $n$ is the total number of monkeys, and $m$ is the total time we observe the monkeys. The next $n$ lines describe the initial situation. The $k$-th line contains two integers, which represent which two monkeys are held by the left hand and the right hand of monkey $k$, respectively. $-1$ means that hand is empty. The next $m$ lines describe the activities we observe. The $i$-th line contains two integers, representing which monkey lets go and which hand it lets go with at time $i - 1$ ($1$ for left, $2$ for right).

Output $n$ integers, one per line, representing the time when each monkey falls to the ground. If it never falls, output `-1`.

Constraints: for all testdata, $1 \le n \le 2 \times 10^5$, $1 \le m \le 4 \times 10^5$. Translated by ChatGPT 5