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.

제한

힌트