题目描述(ID:12118)
标题: 猴子问题
标签: 图结构
详情: 树上有n只猴子。它们编号为 1 到n。1 号猴子用它的尾巴勾着树枝。剩下的猴子都被其他的猴子用手抓着。每只猴子的每只手可以抓住另一只猴子的尾巴。从0 时刻开始,每一秒都有一只猴子松开它的一只手。这会导致一些猴子掉到地上(它们在地上也能继续松开它们的手,猴子落地的时间很短可以不计)。 你的任务是: 写一个程序,从标准输入读入猴子间抓与被抓住的关系信息,和它们放开手的顺 序,对于每一只猴子算出它落地的时间,把结果输出到标准输出。
输入格式:
第一行有两个正整数n和m。n是猴子的数量,m是我们观察猴子的时间(单位为秒)。 
接下来n行是初始情 况的描述。第k+1 行有两个整数表示第k个猴子抓住的猴子的编号,前一个数 代表左手抓的猴子的编号,后一个数是右手抓的猴子的编号。如果读入的数为-1 则代表猴子的手是空的。 
接下来m行是对猴子观察的结果。在这m行里的第i行,有两个整数。前一个是猴子的编号,后一个是它在时刻i−1 时松开的手的编 号(1-左手,2-右手)。
输出格式:
输出n个整数,每行一个。第i行表示第i个猴子落地的时间,如果在观察结束前猴子没有落地,那么输出-1
限制: 30% 1≤n≤1000 ,1≤m≤1000
100% 1≤n≤200000,1≤m≤400000
样例:

输入

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

输出

-1
1
1
登录并解答