A 国和 B 国各有 $ n $ 个机场，两国间有 $ m $ 条航线。
每条航线都有 $ k $ 种不同的备选颜色。保证所有机场起飞的航线数量不超过 $ k $。
第 $ i $ 条航线往返于 A 国的机场 $ u_i $ 和 B 国的机场 $ v_i $，其第 $ j $ 种备选颜色为 $ c_{i, j} $。
给每条航线选择一种备选颜色，使得同一个机场起飞的航线的颜色互不相同。
输入格式
第一行三个整数 $ n, m, k $。
接下来 $ m $ 行，第 $ i $ 行 $ k + 2 $ 个整数 $ u_i, v_i, c_{i, 1}, c_{i, 2}, \cdots, c_{i, k} $。
输出格式
一行 $ m $ 个整数 $ a_1, a_2, \cdots, a_m $，表示第 $ i $ 条航线的颜色为 $ a_i $。
如果有多种方案，给出任意一种即可。保证存在至少一种合法方案。
样例输入
2 4 2 1 1 1 2 1 2 2 3 2 1 1 3 2 2 2 3
样例输出
2 3 3 2
数据范围
保证 $ 1 \leq n, k \leq 150, 1 \leq m \leq n^2, 1 \leq c_{i, j} \leq \min(10^6, mk), 1 \leq u_i, v_i \leq n $。
保证不存在两条航线重合的情况，即不存在 $ 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 $ |