Preparing NOJ # Equivalent Pipelines

3000ms 1048576K

## Description:

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.

## Input:

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:

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.

## Sample Input:

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


## Sample Output:

1 1 3


## Sample Input:

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


## Sample Output:

1 2 1


Info Provider CodeForces Gym

Code GYM103372D

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:45:38

Related

Nothing Yet