#3004. 「JOISC 2015 Day 4」Inheritance

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Chiaki

题目描述

译自 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

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

样例输出 2

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