题目描述(ID:12263)
标题: 猴子
标签: 树结构
详情:
一棵树上有n只猴子,他们都被用1~n的数字做了编号,编号为1的猴子用他的尾巴抓住了一棵树枝,其余的猴子要么被其他猴子抓着,要么抓住了其他猴子或者既被抓着又抓住了别的猴子。每只猴子能用他的两只手并且每只手中最多可抓住一只其他的猴子(抓住他的尾巴)。从0秒开始,每秒钟有一只猴子松开他抓着其他猴子的手。这样有的猴子将掉到地上(猴子在整个落地的过程中所化时间可忽略不计),他们可以继续松开他们抓着其他猴子的手。已知猴子们的初始状态以及它们松手的顺序,计算每只猴子落地的时刻。
输入格式:
输入文件的第一行包含两个整数n和m,1 <= n <= 200000, 1 <= m <= 400000。其中n表示猴子的数量,m表示我们观察猴子的时间(单位为秒)。接下来的n行包含对初始状态的描述,在第k + 1行(1 <= k <= n)是两个整数,表示第K只猴子所抓住的猴子的编号,第一个数表示该猴子左手抓的猴子的编号,第二个数表示右手抓的猴子编号;-1表示猴子的该只手是空的。接下来的m行描述这些猴子松手时的观测结果。在这m行中的第i行(1 <= i <= m)包含两个整数,第一个数表示猴子的编号,第二个数表示在第i - 1秒时该猴子松开的是他紧握的左手还是右手(1代表左手,2代表右手)。
输出格式:
输出文件应包含n个整数,每行输出一个。第i行的数据应表示第i只猴子落地的时间,如果在观测期内该猴子未落地则输出-1。
样例:

输入

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

输出

-1
1
1
登录并解答