湄南河水系是泰国的主要河流系统。其六条最长河流按长度递减排列如下：
- 他钦河 (Tha Chin) (765 km)
- 楠河 (Nan) (740 km)
- 永河 (Yom) (700 km)
- 滨河 (Ping) (658 km)
- 帕萨河 (Pa Sak) (513 km)
- 汪河 (Wang) (335 km)
该河流系统的简化模型如图 F.1 所示，其中较小的红色数字表示每条河流各段的长度。两条或多条河流向下游汇合的点称为汇流点。汇流点用较大的黑色数字标记。在此模型中，每条河流要么终止于一个汇流点，要么流入大海（大海标记为特殊的汇流点编号 0）。当两条或多条河流在汇流点（非 0 号汇流点）汇合时，合并后的河流将沿用其中一条河流的名称。例如，滨河和汪河在 1 号汇流点汇合，合并后的河流保留滨河的名称。按照这种命名方式，滨河的长度为 658 km，而汪河仅为 335 km。如果合并后的河流改名为汪河，那么汪河的长度将变为 688 km，而滨河的长度仅为 305 km。
图 F.1：样例输入 1 中的河流系统。相同颜色的边表示同一条河流。
这种现象引发了河流沿岸城镇之间的激烈竞争。例如，汪河沿岸的居民抗议说，如果采用合适的命名方案，他们的河流实际上可能是最长的，或者至少是第二长的（或者至少不是最后一名！）。为了结束所有猜测，你的任务是验证所有此类主张。
河流的排名是其在按长度递减排序的河流列表中的位置，其中最长河流的排名为 1。对于每条河流，确定其在所有命名方案中能达到的最佳排名。在任何汇流点，任何命名方案中合并后形成的新河流的名称，必须是汇入该汇流点的较小河流之一的名称。如果两条或多条河流在某种命名方案中长度相等，则所有并列的河流都被视为拥有最佳的排名。例如，如果一条河流是最长的，而其他所有河流长度相等，则这些河流的排名均为 2。
输入格式
输入的第一行包含两个整数 $n$ ($1 \le n \le 500\,000$)，表示系统中的河流源头数量，以及 $m$ ($0 \le m \le n - 1$)，表示带有正编号的汇流点数量。这些汇流点的编号从 1 到 $m$。
接下来的 $n$ 行描述河流。每行包含一个字符串，表示源头河流的名称，以及两个整数 $c$ ($0 \le c \le m$) 和 $d$ ($1 \le d \le 10^9$)，其中 $c$ 是下游最近汇流点的标识符，$d$ 是从源头到该汇流点的距离（单位：千米）。河流名称仅使用大小写字母 a–z，长度在 1 到 10 个字符之间（含边界）。
最后 $m$ 行以类似的方式描述汇流点 1 到 $m$。其中第 $k$ 行描述标识符为 $k$ 的汇流点，包含两个整数：下游最近汇流点的标识符以及从汇流点 $k$ 到该汇流点的距离（单位：千米）。
保证每个汇流点 1 到 $m$ 至少两次作为“下游最近汇流点”出现，汇流点 0 至少出现一次，且所有源头均与汇流点 0 相连。
输出格式
按输入顺序，每行输出一条河流的信息。在该行中，显示河流的名称及其最佳可能排名。
样例
输入 1
6 2 PaSak 0 513 Nan 2 675 Yom 2 700 Wang 1 335 Ping 1 305 ThaChin 0 765 0 353 0 65
输出 1
PaSak 5 Nan 2 Yom 1 Wang 3 Ping 4 ThaChin 1