UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4613. [Wf2016]Longest Rivers

统计 下载数据

Description

有n条河流的发源地,有m个汇合点,每个汇合点都有若干条河流汇合,最后所有的河流汇合到一个点。给每个河流
定义一个长度,即从汇合终点开始,遇到分叉即只保留一条主干,剩下的都是支流。现在对于每条河流询问最好可
能的排名。n,m<=500000。

Input

第一行包含两个整数n(1<n<=500000)代表河流源头数,m(0<=m<n)表示汇合点数,这些汇合点被标号为1~m。
接下来n行描述河流,每行包含一个字符串(长度不超过10),表示河流源头的名字,
然后有两个整数c(0<=c<=m)和d(1<=d<=10^9),c表示离其最近的河流下游交汇处的标号,d是到交汇处的距离。
最后m行描述交汇点1~m。每行两个数该交汇点下游最近的交汇点和距离。

Output

输出n行,每行输出河流的名字和最高的可能排名。

Sample Input

6 3
Chi 1 1047
Mekong 2 2650
Mun 1 800
Nan 3 710
Salween 0 2815
Yom 3 787
2 100
0 1700
0 30

Sample Output

Chi 1
Mekong 1
Mun 3
Nan 6
Salween 1
Yom 4

Hint

Source

鸣谢Yts1999上传,lbn187提供译文