TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2107
  • 题目
  • P2107可爱的猴子
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

    样例输入 1

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

    样例输出 1

    -1
    1
    1

    样例输入 2

    10 15
    5 -1
    6 -1
    -1 10
    9 9
    9 10
    -1 7
    10 -1
    5 1
    4 3
    9 3
    6 2
    5 2
    8 1
    5 1
    10 1
    3 2
    4 1
    4 2
    8 2
    1 1
    9 1
    10 2
    7 1
    2 1
    9 2

    样例输出 2

    -1
    0
    3
    3
    9
    0
    3
    8
    3
    3

    提示

    1≤n≤200000,1≤m≤400000


    来源  hzoi