#P18777. [Kaist2021]Equivalent Pipelines

[Kaist2021]Equivalent Pipelines

Equivalent Pipelines

题目描述

你需要用 n−1n-1 条无向水管连接编号为 11 到 nn 的建筑。每条水管连接两个不同建筑,所有建筑必须连通,因此整个管网是一棵树。每条水管有一个正整数耐久度。

对于管网 TT 中两个不同建筑 i,ji,j,定义 vT(i,j)v_T(i,j) 为它们之间唯一路径上所有水管耐久度的最小值。这也等于:在所有拆掉后会使 i,ji,j 不连通的水管中,最小的耐久度。

若对于所有 1≤i<j≤n1\le i<j\le n,两个管网 T1,T2T_1,T_2 都满足 vT1(i,j)=vT2(i,j)v_{T_1}(i,j)=v_{T_2}(i,j),则称它们等价。

现在给出 dd 个管网设计,请将它们按上述等价关系分类。

输入格式

第一行两个整数 d,nd,n。

接下来依次描述 dd 个管网,每个管网占 n−1n-1 行。每行三个整数 a,b,ca,b,c,表示一条连接建筑 a,ba,b、耐久度为 cc 的无向水管。保证每个管网均为树。

输出格式

输出一行 dd 个整数。第 ii 个整数是所有与第 ii 个管网等价的管网中,最小的输入编号。管网编号从 11 开始。

数据范围

  • d≥1d\ge1,n≥2n\ge2,dn≤500000dn\le500000。
  • 1≤a,b≤n1\le a,b\le n,a≠ba\ne b,1≤c≤1091\le c\le10^9。

样例 1

输入

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

输出

1 1 3

样例 2

输入

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