Сегодня Джонни хочет увеличить свой вклад. Его план подразумевает написание \(n\) блогов. Один блог покрывает одну тему, но одна тема может быть покрыта несколькими блогами. Также, некоторые блоги связаны друг с другом ссылками. Каждая пара блогов, связанных ссылкой, должна покрывать две разные темы. Потому что иначе читатели могут заметить, что блоги разделены только для того, чтобы набрать больше вклада. Множество блогов и двусторонние ссылки между некоторыми парами из них называются сетью блогов.
Всего есть \(n\) различных тем, пронумерованных от \(1\) до \(n\), упорядоченных по пониманию Джонни. Структура сети блогов уже приготовлена. Теперь Джонни должен написать все блоги в некотором порядке. Он ленивый, поэтому каждый раз перед написанием блога, он смотрит на все уже написанные соседние блоги (связанные ссылкой с текущим) и выбирает тему с минимальным номером, которая еще не покрыта соседними блогами. Можно заметить, что такая стратегия всегда позволит ему выбрать тему, потому что максимальное количество соседних блогов равно \(n - 1\).
Например, если уже написанные, соседние с текущим, блоги покрывают темы с номерами \(1\), \(3\), \(1\), \(5\) и \(2\), Джонни выберет тему номер \(4\) для текущего блога, потому что темы номер \(1\), \(2\) и \(3\) уже покрыты соседними блогами, а тема номер \(4\) — нет.
Как хороший друг, вы провели некоторые исследования и предсказали наилучшую темы для каждого блога. Не могли бы вы сказать Джонни, в каком порядке он должен писать блоги, чтобы в результате его стратегии каждый блог покрывал выбранную вами тему?
Выходные данные
Если решение не существует, выведите \(-1\). Иначе, выведите \(n\) различных целых чисел \(p_1, p_2, \ldots, p_n\) \((1 \leq p_i \leq n)\), которые обозначают номера блогов в том порядке, в котором Джонни должен их написать. Если существует несколько решений, выведите любое.
Примечание
В первом примере, Джонни начинает с написания блога номер \(2\), у него пока еще нет написанных соседних блогов, поэтому Джонни выбирает тему номер один. Потом он пишет блог номер \(1\), у него есть ссылка на уже написанный второй блог, поэтому Джонни выбирает вторую тему. Наконец, он пишет блог номер \(3\), у него есть ссылки на блоги номер \(1\) и \(2\), поэтому Джонни выбирает третью тему.
Второй пример: Не существует ни одной перестановки, удовлетворяющей всем условиям.
Третий пример: Сначала Джонни пишет блог номер \(2\), который получает тему \(1\). Затем, он пишет блог \(5\), который тоже получает тему \(1\), потому из него нет ссылки на единственный уже написанный блог (номер \(2\)). Затем, он пишет блог \(1\), он получает тему \(2\), потому что из него есть ссылка на блог \(2\) с темой \(1\). Затем, он пишет блог \(3\), из него есть ссылка на блог \(2\), поэтому он получает тему \(2\). Наконец, он пишет блог \(4\), из него есть ссылка на блог \(5\), поэтому он получает тему \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2
2 3
3 1
2 1 3
|
2 1 3
|
|
2
|
3 3
1 2
2 3
3 1
1 1 1
|
-1
|
|
3
|
5 3
1 2
2 3
4 5
2 1 2 2 1
|
2 5 1 3 4
|