A 国和 B 国各有 n 个机场,两国间有 m 条航线。
每条航线都有 k 种不同的备选颜色。保证所有机场起飞的航线数量不超过 k。
第 i 条航线往返于 A 国的机场 ui 和 B 国的机场 vi,其第 j 种备选颜色为 ci,j。
给每条航线选择一种备选颜色,使得同一个机场起飞的航线的颜色互不相同。
输入格式
第一行三个整数 n,m,k。
接下来 m 行,第 i 行 k+2 个整数 ui,vi,ci,1,ci,2,⋯,ci,k。
输出格式
一行 m 个整数 a1,a2,⋯,am,表示第 i 条航线的颜色为 ai。
如果有多种方案,给出任意一种即可。保证存在至少一种合法方案。
样例输入
2 4 2 1 1 1 2 1 2 2 3 2 1 1 3 2 2 2 3
样例输出
2 3 3 2
数据范围
保证 1≤n,k≤150,1≤m≤n2,1≤ci,j≤min。
保证不存在两条航线重合的情况,即不存在 i \neq j 满足 (u_i, v_i) = (u_j, v_j) 。
子任务编号 | 特殊性质 | 分值 |
---|---|---|
1 | k = 1 | 1 |
2 | k = 2n | 2 |
3 | k = 2 | 11 |
4 | m = n^2, k = n + 1 | 37 |
5 | m = n^2 | 21 |
6 | 无 | 28 |