[Wf2016]Longest Rivers
时间限制：100s 空间限制：1024MB
题目描述
有n条河流的发源地，有m个汇合点，每个汇合点都有若干条河流汇合，最后所有的河流汇合到一个点。给每个河流
定义一个长度，即从汇合终点开始，遇到分叉即只保留一条主干，剩下的都是支流。现在对于每条河流询问最好可
能的排名。n,m<=500000。
输入格式
第一行包含两个整数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。每行两个数该交汇点下游最近的交汇点和距离。
输出格式
输出n行，每行输出河流的名字和最高的可能排名。
样例输入
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
样例输出
Chi 1 Mekong 1 Mun 3 Nan 6 Salween 1 Yom 4
提示
没有写明提示
题目来源
鸣谢Yts1999上传，lbn187提供译文