21643번 - New Level 스페셜 저지다국어

Robocity has $n$ crossroads connected by bidirectional roads. There are $m$ roads in total, and all crossroads are reachable from each other. There is a level assigned to each crossroad specified by a number from $1$ to $k$, inclusive. Any pair of crossroads directly connected by a road has distinct levels.

The city leaders are planning a reform. Namely, they want to assign new levels to crossroads, so that each level still has a value from $1$ to $k$, connected crossroads would have different levels, and an additional condition has to be met: for each pair of crossroads $u$ and $v$ there must exist a path between them, such that any two adjacent crossroads along it have levels that differ by $1$ modulo $k$. 

Formally, for each pair of crossroads $(u, v)$ there should exist a sequence of crossroads $p_1, \ldots, p_l$, such that:

• $p_1=u$;
• $p_l=v$;
• for each $i$ from $1$ to $l-1$, crossroads $p_i$ and $p_{i+1}$ are connected, and either their levels differ by one, or one of them has level of $1$ and another has level of $k$.

Robocity government is convinced that such level assignment exists and asks you to find it. 

The first line contains three integers $n$, $m$, $k$ ($1 \le n, m, k \le 500000$), number of crossroads, roads, and levels.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le k$), $c_i$ is the level of the crossroad $i$.

Then $m$ lines follow, each of them contains two integers $u$, $v$ ($1 \le u, v \le n, u \neq v$), a pairs of crossroads connected by a road.

It is guaranteed that there are no two roads connecting the same pair of crossroads, and that there exists a path between each pair of crossroads.

Output $n$ integers $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le k$), the levels of the crossroads in the new assignment.