Вам задана перестановка чисел 1, 2, ..., n, а также m пар позиций (aj, bj).
На каждом шагу вы можете выбрать некоторую пару из заданного набора и поменять местами числа на этих позициях. Найдите лексикографически максимальную перестановку, которую можно получить такими операциями.
Пусть p и q — это две перестановки чисел 1, 2, ..., n. Перестановка p считается лексикографически меньше перестановки q, если существует число 1 ≤ i ≤ n такое, что pk = qk для всех 1 ≤ k < i и pi < qi.
Выходные данные
Выведите строку с n различными целыми числами p'i (1 ≤ p'i ≤ n) — лексикографически максимальную перестановку, которую можно получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
|
7 8 9 4 5 6 1 2 3
|