QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+1]
Statistics

A 国和 B 国各有 n 个机场,两国间有 m 条航线。

每条航线都有 k 种不同的备选颜色。保证所有机场起飞的航线数量不超过 k

i 条航线往返于 A 国的机场 ui 和 B 国的机场 vi,其第 j 种备选颜色为 ci,j

给每条航线选择一种备选颜色,使得同一个机场起飞的航线的颜色互不相同。

输入格式

第一行三个整数 n,m,k

接下来 m 行,第 ik+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

数据范围

保证 1n,k150,1mn2,1ci,jmin

保证不存在两条航线重合的情况,即不存在 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