2043. [POI 2003]可爱的猴子

【题目描述】

有$n$只猴子，第一只尾巴挂在树上，剩下的$n-1$只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。

当然一只猴子最多抓两只另外的猴子，因为只有两只猴爪子嘛。

现在给出这$n$只猴子抓与被抓的信息，并且在某个时刻可能某只猴子会放掉它左手或右手的猴子，导致某些猴子落在地上。

求每只猴子落地的时间。

【输入格式】

第一行两个$n,m(n\leq 2\times 10^5,m\leq 4\times 10^5)$，表示有$n$只猴子，并且总时间为$m-1$。

接下来$n$行，描述了每只猴子的信息，每行两个数，分别表示这只猴子左手和右手抓的猴子的编号，如果是$-1$，表示该猴子的那只手没抓其他的猴子。

再接下来$m$行，按时间顺序给出了一些猴子放手的信息，第$i$行表示$i-1$时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子的编号，后者表示其放的是哪只手，$1$表示左手，$2$表示右手。

【输出格式】

共输出$n$行，第$i$行表示第$i$只猴子掉落的时刻，若第$i$只猴子$m-1$时刻以后还没掉落，就输出$-1$。

【样例输入】

3 2
-1 3
3 -1
1 2
1 2
3 1

【样例输出】

-1
1
1