Football
Contest: Codeforces Round 591 (Div. 1, based on Technocup 2020 Elimination Round 1)
Difficulty rating: 3100
Tags: graphs

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
One of possible solutions to the example is shown below:

Example input:
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

Example output:
3
2
1
1
3
1
2
1
2
3
2

Editorial:
Let's assume that $$$m \leq n \cdot k$$$.
We can randomly assign colors to edges. If there is a vertex that does not satisfy the condition, then we can choose color $$$a$$$ which appears the smallest number of times and color $$$b$$$ which appears the biggest number of times. We will "recolor" edges that have one of these two colors.
Let's consider this graph only with edges with colors $$$a$$$ and $$$b$$$. Let's add a "fake" vertex $$$0$$$. This graph may have many components. If a component has at least one vertex with odd degree, we connect each such vertex with $$$0$$$. Otherwise, let's choose any vertex from that component and add two edges to $$$0$$$. Therefore, the graph will be connected and each vertex will have an even degree. Thus, we will be able to find an Euler cycle. Let's color the odd edges in the cycle in $$$a$$$, and even edges in $$$b$$$. As a result, the difference between these two colors for each vertex will be at most $$$1$$$.
Let's do this operation while there is a vertex which does not satisfy the condition.
If $$$m > n \cdot k$$$, let's split the edges into two groups with the equal sizes (that is, $$$\lfloor \frac{m}{2} \rfloor$$$ and $$$\lceil \frac{m}{2} \rceil$$$). If a group has not greater than $$$n \cdot k$$$ edges, then do the algorithm at the beginning of the tutorial. Otherwise, split it again.
If you found the answers for two groups, you need to find the answer for the combined graph. Let $$$f_1$$$ be the most popular color in the first group, $$$f_2$$$ the second most popular color, ..., $$$f_k$$$ the least popular color in the first group. Similarly, let $$$g_1$$$ be the most popular color in the second graph, etc. So, in the combined graph, $$$f_1$$$ should be equal to $$$g_k$$$, $$$f_2$$$ should be equal to $$$g_{k-1}$$$. In other words, we take the most popular color in the first group and color the least popular color in the second group with that color. If there is a vertex that does not satisfy the condition, "recolor" the graph according to the algorithm explained in the third paragraph.