Football

题意翻译

### 题目描述 世界上有 $n$ 个球队。 足球主席委员会（MFO）想主持最多 $m$ 场足球赛，MFO 希望第 $i$ 场比赛在球队 $a_i$ 和 $b_i$ 之间举办，举办场地为 $k$ 个体育场中的一个。 命名 $s_{i,j}$ 为第 $i$ 个队伍在第 $j$ 个体育场打的比赛的数量。MFO 不希望一个队伍在一个体育场打的比赛远多于在其他体育场打的比赛。所以，对于每一个队伍 $i$ ，其 $s_{i,1},s_{i,2},……,s_{i,k}$ 中，最大值和最小值的差的绝对值不应该超过 $2$。 每个队伍有一个 $w_i$ ，表示第 $i$ 个队伍每打一场比赛 MFO 赚取的收益。如果队伍 $i$ 打了 $l$ 场比赛，那么 MFO 将会获得 $w_i*l$ 的钱。 MFO 需要知道他们应该在哪个体育场举办哪一场比赛，使得在不违反他们设定的规则的前提下，赚取尽可能多的钱 然而这个问题对于 MFO 来说太复杂了，因此需要你的帮助。 ### 输入格式 第一行包含三个整数 $n,m,k\ \ (3≤n≤100, 0≤m≤1000, 1≤k≤1000)$. 第二行包含 $n$ 个整数 $w_1,w_2,……,w_n\ \ (1≤w_i≤1000)$ ，意义见题目描述。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i\ \ (1≤a_i,b_i≤n,\ a_i\neq b_i)$ ，意义见题目描述。 ### 输出格式 对于每场比赛，输出 $t_i\ (1≤t_i≤k) $，表示这场比赛在第 $t_i$ 个体育场举行，如果第 $i$ 场比赛不应该被举办，则 $t_i=0$.

题目描述

There are $ n $ football teams in the world. The Main Football Organization (MFO) wants to host at most $ m $ games. MFO wants the $ i $ -th game to be played between the teams $ a_i $ and $ b_i $ in one of the $ k $ stadiums. Let $ s_{ij} $ be the numbers of games the $ i $ -th team played in the $ j $ -th stadium. MFO does not want a team to have much more games in one stadium than in the others. Therefore, for each team $ i $ , the absolute difference between the maximum and minimum among $ s_{i1}, s_{i2}, \ldots, s_{ik} $ should not exceed $ 2 $ . Each team has $ w_i $ — the amount of money MFO will earn for each game of the $ i $ -th team. If the $ i $ -th team plays $ l $ games, MFO will earn $ w_i \cdot l $ . MFO needs to find what games in what stadiums they need to host in order to earn as much money as possible, not violating the rule they set. However, this problem is too complicated for MFO. Therefore, they are asking you to help them.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , $ k $ ( $ 3 \leq n \leq 100 $ , $ 0 \leq m \leq 1\,000 $ , $ 1 \leq k \leq 1\,000 $ ) — the number of teams, the number of games, and the number of stadiums. The second line contains $ n $ integers $ w_1, w_2, \ldots, w_n $ ( $ 1 \leq w_i \leq 1\,000 $ ) — the amount of money MFO will earn for each game of the $ i $ -th game. Each of the following $ m $ lines contains two integers $ a_i $ and $ b_i $ ( $ 1 \leq a_i, b_i \leq n $ , $ a_i \neq b_i $ ) — the teams that can play the $ i $ -th game. It is guaranteed that each pair of teams can play at most one game.

输出格式

For each game in the same order, print $ t_i $ ( $ 1 \leq t_i \leq k $ ) — the number of the stadium, in which $ a_i $ and $ b_i $ will play the game. If the $ i $ -th game should not be played, $ t_i $ should be equal to $ 0 $ . If there are multiple answers, print any.

输入输出样例

输入样例 #1

7 11 3
4 7 8 10 10 9 3
6 2
6 1
7 6
4 3
4 6
3 1
5 3
7 5
7 3
4 2
1 4

输出样例 #1

3
2
1
1
3
1
2
1
2
3
2

说明

One of possible solutions to the example is shown below: