#1817. 彩虹航线

    ID: 1817 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1456来源:qoj.ac数据:公开样例贪心枚举

彩虹航线

彩虹航线

题目描述

标题: 彩虹航线 - Problem - QOJ.ac

#7977. 彩虹航线

Statistics

The problem was used in the following contests:

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(106,mk),1≤ui,vi≤n。

保证不存在两条航线重合的情况,即不存在 i≠j 满足 (ui,vi)=(uj,vj)。

子任务编号特殊性质分值1k=112k=2n23k=2114m=n2,k=n+1375m=n2216无28

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 4 2
1 1 1 2
1 2 2 3
2 1 1 3
2 2 2 3
2 3 3 2