You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

IOI 国所有铁路的拥有者、大富豪 JOI 先生已经去世。根据遗嘱，铁路将被分割并继承。

IOI 国有 $N$ 个城市，以及连接这些城市的 $M$ 条铁路。城市编号为 1 到 $N$，铁路编号为 1 到 $M$。第 $i$ 条铁路连接城市 $A_i$ 和城市 $B_i$，为双向线路，每年可产生 $C_i$ 日元的收益。由于乘客数量和票价各异，$C_1, \dots, C_M$ 各不相同。可能存在多条铁路连接同一对城市。

遗嘱中规定了铁路分割继承的方法如下：

• 铁路将由 JOI 先生的 $K$ 个子女继承。子女按年龄从高到低依次编号为 1 到 $K$。
• 每个子女继承若干条铁路（可能为 0 条）。
• 首先，从 $M$ 条铁路中，子女 1 选择若干条作为自己的继承部分；接着，从剩余铁路中，子女 2 决定自己的继承部分；依此类推，$K$ 个子女依次决定继承部分。
• 任何子女都不能继承已被更年长子女继承的铁路。即，若铁路 $i$ 已被子女 $j$ 继承，则任何更年轻的子女 $k$（$k > j$）均不能继承该铁路。
• 任何子女在选择继承部分时，必须确保所选铁路不构成环路。即，若存在一条由铁路 $i_1, i_2, \dots, i_m$（其中 $i_1, i_2, \dots, i_m$ 互不相同）组成的路径，使得从某个城市出发，经过这些铁路后能返回原城市，则任何子女均不能独自继承所有这些铁路。
• 未被任何子女继承的铁路将捐赠给 IOI 国。

每个子女都像其父亲一样贪婪，希望自己的继承部分的年收益总和尽可能大。已证明，对于每个子女，存在唯一一种选择方式，使其继承部分的年收益总和达到最大值。请确定每条铁路由谁继承。

题目

给定 IOI 国铁路的信息和 JOI 先生子女的人数，编写程序求出每条铁路由谁继承。

输入格式

从标准输入读取以下内容：

• 第一行包含三个整数 $N, M, K$，以空格分隔。这表示 IOI 国有 $N$ 个城市和 $M$ 条铁路，JOI 先生有 $K$ 个子女。
• 接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含三个整数 $A_i, B_i, C_i$，以空格分隔。这表示第 $i$ 条铁路连接城市 $A_i$ 和城市 $B_i$（双向），年收益为 $C_i$ 日元。

输出格式

输出共 $M$ 行。第 $i$ 行（$1 \le i \le M$）输出继承第 $i$ 条铁路的子女编号。若该铁路被捐赠给 IOI 国，则输出 0。

3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

1
0
2
1
2

3 6 5
1 2 1
1 2 2
2 3 3
2 3 4
3 1 5
3 1 6

4
3
2
1
2
1

提示

样例 1 解释

• 子女 1 从铁路 1, 2, 3, 4, 5 中选择铁路 1 和 4 进行继承。此时继承铁路的年收益总和为 $3 + 6 = 9$ 日元，这是最大值。
• 子女 2 从剩余铁路 2, 3, 5 中选择铁路 3 和 5 进行继承。此时继承铁路的年收益总和为 $4 + 2 = 6$ 日元，这是最大值。
• 剩余铁路 2 将捐赠给 IOI 国。

样例 2 解释

继承铁路的数量可能因子女而异。可能存在完全没有继承任何铁路的子女。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 1000$
• $1 \le M \le 300000$
• $1 \le K \le 10000$
• $1 \le A_i \le N$, $1 \le B_i \le N$（$1 \le i \le M$）
• $A_i \ne B_i$（$1 \le i \le M$）
• $1 \le C_i \le 1000000000$（$1 \le i \le M$）
• $C_i \ne C_j$（$1 \le i < j \le M$）

子任务

子任务 1 [15 分]

• $K \le 10$

子任务 2 [85 分]

无额外限制。

翻译由 Qwen3-235B 完成