#3004. 「JOISC 2015 Day 4」Inheritance

---

题目描述

译自 JOISC 2015 Day4 T1「Inheritance」。

有一个 $N$ 个点 $M$ 条边的无向图。第 $i$ 条边连接 $A_i$ 和 $B_i$，边权为 $C_i$，保证 $C_i$ 互不相同。

现在有 $K$ 个人，依次从 $1$ 到 $K$ 编号。第 $1$ 个人先操作，会删掉图里一个边权和最大生成森林。然后是第 $2$ 个人，会删掉剩下图里一个边权和最大生成森林。依次类推，接下来是第 $3$ 个人，第 $4$ 个人，……，直到第 $K$ 个人。对于每条边，你需要求出它是被哪个人删掉的。

---

输入格式

第一行包含三个整数 $N$，$M$ 和 $K$，含义如题面所述。

接下里 $M$ 行，第 $i$ 行包含三个整数 $A_i$，$B_i$ 和 $C_i$，表示第 $i$ 条边连接 $A_i$ 和 $B_i$，边权为 $C_i$。

---

输出格式

输出 $M$ 行，第 $i$ 行包含一个整数，表示第 $i$ 条边被哪个人删除了。如果第 $i$ 条边没有被删除，输出 $0$。

---

样例 1

输入

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

输出

1
0
2
1
2

---

样例 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

---

数据范围与提示

对于全部数据，满足 $2 \le N \le 1000$，$1 \le M \le 3 \times 10^5$，$1 \le K \le 10^4$，$1 \le A_i, B_i \le N$，$1 \le C_i \le 10^9$，保证 $C_i$ 互不相同。

本题共有 $2$ 个子任务。每个子任务的分数和附加限制如下：

Subtask	附加限制	分数
1	$K \le 10$	$15$
2	无附加限制	$85$