C0692 [SDOI2017]天才黑客

SD0062 号选手小 Q 同学为了偷到 SDOI7012 的试题，利用高超的黑客技术潜入了 SDOI 出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这让小 Q 同学感觉有些棘手， 不过这根本难不倒他，很快他就分析出了整个内联网的结构。

内联网中有 $n$ 个节点（从 $1$ 到 $n$ 标号）和 $m$ 条单向网线，中央控制系统在第 $1$ 个节点上，每条网线单向连接内联网中的某两个节点，从 $1$ 号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序，应用程序会携带一条通信口令，当且仅当程序的口令与网线的口令相同时，程序才能通过这条网线到达另一端的节点继续运行，并且通过每条网线都需要花费一定的时间。

每个应用程序可以在任意一个节点修改通信口令，修改通信口令花费的时间可以忽略不计，但是为了减小修改量，需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀（记其长度为 $\text{len}$），由于获取网线的口令的某个字符会比较耗时，调用一次这个子程序需要花费 $\text{len}$ 个单位时间。

除此之外，小 Q 同学还在中央控制系统中发现了一个字典，每条网线的口令都是字典中的某个字符串。具体来说，这个字典是一棵 $k$ 个节点（从 $1$ 到 $k$ 标号）的有根树，其中根是第 $1$ 个节点，每条边上有一个字符，字符串 $S$ 在字典中当且仅当存在某个点 $u$ 使得从根节点出发往下走到 $u$ 的这条路径上的字符顺次拼接构成 $S$。

现在小 Q 同学在$1$号节点同时开启了 $n − 1$ 个应用程序，这些应用程序同时运行且互不干扰，每个程序的通信口令都为空，他希望用最短的时间把这些程序分别发送到其他节点上，你需要帮小 Q 同学分别计算出发送到第 $i(= 2, 3, \dots, n)$ 个节点的程序完成任务的最短时间。

样例输入 1

1
4 4 6
1 2 2 5
2 3 2 5
2 4 1 6
4 2 1 6
1 2 1
2 3 1
3 4 1
4 5 2
1 6 2

样例输出 1

2
7
3