23172번 - Equivalent Pipelines 다국어

문제

You are planning to construct a water pipeline network, connecting $n$ buildings in KAIST. Due to budget problems, you can only use $n-1$ pipes. Each pipe is undirected and connects two different buildings, and all $n$ buildings must be pairwise connected through some sequence of pipes. These pipes form a network.

As a careful planner, you designed $d$ different networks and want to compare them. One can describe each pipe in the network with a durability, which is a single positive integer. Given a network $T,ドル define the vulnerability $v_{T}(i, j)$ of two distinct buildings $i$ and $j$ to be the minimum durability of a pipe whose removal separates buildings $i$ and $j$. In other words, $v_{T}(i, j)$ is the minimum durability over all pipes on the path connecting $i$ to $j$.

If two networks $T_{1}$ and $T_{2}$ satisfy $v_{T_1}(i, j) = v_{T_2}(i, j)$ for all 1ドル \le i < j \le n,ドル we say $T_{1}$ and $T_{2}$ are equivalent. To filter out unnecessary plans, group the $d$ designs up to equivalency.

입력

The first line contains two integers $d$ and $n$ ($d \ge 1,ドル $n \ge 2,ドル $d\cdot n \le 500,000円$), separated by a space.

From the second line, the descriptions for the $d$ designs are given. Each design is described over $n-1$ lines, each line consisting of three integers $a,ドル $b$ and $c$ (1ドル \le a, b \le n,ドル $a \neq b,ドル 1ドル \le c \le 10^{9}$), indicating there is a pipe connecting buildings $a$ and $b$ directly, whose durability is equal to $c$.

출력

Output $d$ integers in a line. For 1ドル \le i \le d,ドル the $i$-th number should be the minimum index $j,ドル where the $j$-th network in the input is equivalent to the $i$-th network in the input.

제한

힌트