P6560: 可爱的猴子
传统题
1.000s
时间限制
128MB
内存限制
1 提交
1 解决
【题目描述】
树上有n只猴子。它们编号为1到n。1号猴子用它的尾巴勾着树枝。剩下的猴子都被其他的猴子用手抓着。每只猴子的每只手可以抓住另一只猴子的尾巴。从0时刻开始，每一秒都有一只猴子松开它的一只手。这会导致一些猴子掉到地上（它们在地上也能继续松开它们的手，猴子落地的时间很短可以不计）。
你的任务是：
写一个程序，从标准输入读入猴子间抓与被抓住的关系信息，和它们放开手的顺序，对于每一只猴子算出它落地的时间，把结果输出到标准输出。
【输入】
标准输入的第一行有两个正整数n和m，1<=n<=200000,1<=m<=400000。n是猴子的数量，m是我们观察猴子的时间（单位为秒）。接下来n行是初始情况的描述。第k+1行有两个整数表示第k个猴子抓住的猴子的编号，前一个数代表左手抓的猴子的编号，后一个数是右手抓的猴子的编号。如果读入的数为-1则代表猴子的手是空的。接下来m行是对猴子观察的结果。在这m行里的第i行，有两个整数。前一个是猴子的编号，后一个是它在时刻i-1时松开的手的编号（1-左手，2-右手）。
【输出】
你应该输出n个整数，每行一个。第i行表示第i个猴子落地的时间，如果在观察结束前猴子没有落地，那么输出-1。
【样例输入】复制
3 2
-1 3
3 -1
1 2
1 2
3 1
【提示】
第一只猴子松开手时是0时刻