408875: GYM103371 C 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.

3 3
1 2 1
1 3 1
1 2 1
2 3 1
1 2 1
2 3 2

1 1 3 

3 4
1 2 2
2 3 1
3 4 2
1 3 2
2 4 2
2 3 1
1 2 2
1 3 1
3 4 2

1 2 1