Description

湄南河系统是泰国的主要河流系统。按长度递减排列的六条最长的河流是：

Tha Chin（$765$ 公里）

Nan（$740$ 公里）

Yom（$700$ 公里）

Ping（$658$ 公里）

Pa Sak（$513$ 公里）

Wang（$335$ 公里）

图 1 展示了该河流系统的简化模型，其中较小的红色数字表示各河段的长度。两个或多个河流在下游汇合的点称为汇合点。汇合点用较大的黑色数字标记。在这个模型中，每条河流要么在汇合点结束，要么流入大海，流入大海的汇合点标记为特殊的汇合点编号 $0$。当两条或多条河流在汇合点（汇合点 $0$ 除外）汇合时，合并后的河流会取其中一条河流的名字。例如，Ping 和 Wang 在汇合点 $1$ 汇合，合并后的河流保留了 Ping 的名字。这样命名下，Ping 的长度为 $658$ 公里，而 Wang 只有 $335$ 公里。如果合并后的河流命名为 Wang，那么 Wang 的长度将为 $688$ 公里，而 Ping 的长度只有 $305$ 公里。

图 1：样例输入 1 中的河流系统。同色的边表示一条河流。

对这一现象的关注引发了沿河城镇之间的激烈竞争。例如，沿 Wang 河的居民抗议说，也许通过适当的命名方案，他们的河流实际上可能是最长的，或者可能是第二长的（至少不是最后一名！）。为了结束所有的猜测，你的任务是验证所有这样的说法。

河流的排名是按长度递减排列的所有河流中的位置，最长的河流排名为 $1$。对于每条河流，确定在所有命名方案中其可能的最佳排名。在任何汇合点，任何命名方案中新、较大的河流的名称必须是该汇合点汇合的较小河流之一的名称。如果在某个命名方案中两条或多条河流长度相等，则所有并列的河流被视为具有可能的最佳排名。例如，如果一条河流是最长的，而所有其他河流相等，则这些河流的排名均为 $2$。

Input Format

输入的第一行包含两个整数 $n$ $(1 \le n \le 500\, 000)$，表示系统中的河流源数量，以及 $m$ $(0 \le m \le n - 1)$，表示带有正标签的汇合点数量。这些汇合点编号从 $1$ 到 $m$。

接下来的 $n$ 行描述了河流。每行由一个字符串（表示河流源头的名称）和两个整数 $c$ $(0 \leq c \leq m)$ 和 $d$ $(1 \leq d \leq 10^9)$ 组成，其中 $c$ 是下游最近的汇合点的标识符，$d$ 是从源头到该汇合点的距离（以公里为单位）。河流名称仅使用小写和大写字母 a–z，长度在 $1$ 到 $10$ 个字符之间（含）。

最后的 $m$ 行以类似的方式描述了汇合点 $1$ 到 $m$。第 $k^\text {th}$ 行描述了标识符为 $k$ 的汇合点，并包含两个整数：下游最近的汇合点的标识符和从汇合点 $k$ 到该汇合点的距离（以公里为单位）。

保证每个汇合点 $1$ 到 $m$ 至少出现两次作为“下游最近的汇合点”，汇合点 $0$ 至少出现一次，并且所有源头都连接到汇合点 $0$。

Output Format

按输入顺序每行显示一条河流。在该行上，显示河流的名称及其可能的最佳排名。

6 2
PaSak 0 513
Nan 2 675
Yom 2 700
Wang 1 335
Ping 1 305
ThaChin 0 765
0 353
0 65

PaSak 5
Nan 2
Yom 1
Wang 3
Ping 4
ThaChin 1

Hint

时间限制：9000 毫秒，内存限制：1048576 KB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。

题面翻译由 ChatGPT-4o 提供。