QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
统计

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 $