← 返回题目列表

Codeforces · 1240/F

F. 足球

中文机器翻译题面 查看原题

世界上有 $$$n$$$ 足球队。

主要足球组织 (MFO) 希望举办最多 $$$m$$$ 场比赛。 MFO 希望第 $$$i$$$ 场比赛在 $$$a_i$$$ 队和 $$$b_i$$$ 队之间在 $$$k$$$ 体育场之一进行。

令 $$$s_{ij}$$$ 为第 $$$i$$$ 队在第 $$$j$$$ 个体育场进行的比赛场数。 MFO 不希望一支球队在一个体育场举行的比赛比在其他体育场举行的比赛多得多。因此,对于每个团队$$$i$$$,$$$s_{i1}、s_{i2}、\ldots、s_{ik}$$$之间的最大值和最小值之间的绝对差值不应超过$$$2$$$。

每个团队都有 $$$w_i$$$ — MFO 在第 $$$i$$$ 团队的每场比赛中赚取的金额。如果第 $$$i$$$ 队伍参加 $$$l$$$ 比赛,MFO 将赚取 $$$w_i \cdot l$$$。

MFO 需要找到他们需要在哪些体育场馆举办哪些比赛,以便赚取尽可能多的钱,而不违反他们制定的规则。

然而,这个问题对于MFO来说太复杂了。因此,他们请求您帮助他们。

输入

第一行包含三个整数 $$$n$$$, $$$m$$$, $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq m \leq 1\,000$$$, $$$1 \leq k \leq 1\,000$$$) — 球队数量,比赛数量,以及体育场的数量。

第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \leq w_i \leq 1\,000$$$) — MFO 在第 $$$i$$$ 游戏的每场游戏中赚取的金额。

以下 $$$m$$$ 行中的每一行都包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) - 可以参加第 $$$i$$$ 场比赛的球队。保证每对球队最多可以进行一场比赛。

输出

对于相同顺序的每场比赛,打印 $$$t_i$$$ ($$$1 \leq t_i \leq k$$$) — $$$a_i$$$ 和 $$$b_i$$$ 将参加比赛的体育场号码。如果不应玩第 $$$i$$$ 游戏,$$$t_i$$$ 应等于 $$$0$$$。

如果有多个答案,请打印其中一个。

示例

输入 #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

注意

该示例的可能解决方案之一如下所示: