问题 25329 --可爱的猴子

25329: 可爱的猴子

时间限制: 1 Sec  内存限制: 128 MB
提交: 37  解决: 19
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][18176kb]

题目描述

      树上有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

样例输出

-1
1
1

提示

第一只猴子松开手时是0时刻

来源

[提交][状态]