Задача №114864. Новый уровень
В Робосити \(n\) перекрестков, некоторые из которых соединены двусторонними дорогами. Всего в Робосити \(m\) дорог, от каждого перекрестка можно добраться до любого другого по дорогам. Каждому перекрестку присвоен уровень, который задаётся целым числом от от \(1\) до \(k\) включительно. При этом перекрестки, соединенные дорогой, всегда имеют различные уровни.
Руководство города планирует произвести реформу. А именно, оно хочет назначить перекресткам новые уровни, чтобы каждый уровень по прежнему имел бы значение от \(1\) до \(k\), перекрестки, соединенные дорогой, имели различные уровни, и выполнялось дополнительное условие. Между каждой парой перекрестков \(u\) и \(v\) должен существовать путь по дорогам, такой что любые два соседних перекрестка в нем имеют уровень, отличающийся на \(1\) по модулю \(k\).
Формально, для каждой пары перекрестков \((u, v)\) должна существовать последовательность перекрестков \(p_1, \ldots, p_l\), в которой выполняются условия:
- \(p_1=u\);
- \(p_l=v\);
- для всех \(i\) от \(1\) до \(l-1\) перекрестки \(p_i\) и \(p_{i+1}\) соединены дорогой, и их уровни различаются ровно на один, либо один из них имеет уровень \(1\), а другой — \(k\).
Руководство Робосити уверено, что такое назначение уровней существует, и просит вас его найти.
В первой строке записаны три целых числа \(n\), \(m\), \(k\) (\(1 \le n, m, k \le 500\,000\)) — количества перекрестков, дорок и уровней, соответственно.
Во второй строке записаны \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le k\)), \(c_i\) обозначает уровень перекрестка с номером \(i\).
В последующих \(m\) строках записаны по два числа \(u\), \(v\) (\(1 \le u, v \le n\); \(u \neq v\)), обозначающие номера перекрестков, соединенных дорогой.
Гарантируется, что любые два перекрестка соединены не более чем одной дорогой, и что от любого перекрестка можно добраться до любого другого по дорогам.
Выведите \(n\) чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le k\)) — новые уровни перекрестков.
4 4 4 1 2 3 1 1 2 1 3 2 3 3 4
2 3 4 1