#P18777. [Kaist2021]Equivalent Pipelines
[Kaist2021]Equivalent Pipelines
Equivalent Pipelines
题目描述
你需要用 条无向水管连接编号为 到 的建筑。每条水管连接两个不同建筑,所有建筑必须连通,因此整个管网是一棵树。每条水管有一个正整数耐久度。
对于管网 中两个不同建筑 ,定义 为它们之间唯一路径上所有水管耐久度的最小值。这也等于:在所有拆掉后会使 不连通的水管中,最小的耐久度。
若对于所有 ,两个管网 都满足 ,则称它们等价。
现在给出 个管网设计,请将它们按上述等价关系分类。
输入格式
第一行两个整数 。
接下来依次描述 个管网,每个管网占 行。每行三个整数 ,表示一条连接建筑 、耐久度为 的无向水管。保证每个管网均为树。
输出格式
输出一行 个整数。第 个整数是所有与第 个管网等价的管网中,最小的输入编号。管网编号从 开始。
数据范围
- ,,。
- ,,。
样例 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