C. Круг чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася написал на доске по кругу в некотором порядке n различных целых чисел от 1 до n. Затем он соединил дугами пары чисел (a, b) (a ≠ b), которые либо являются непосредственными соседями друг друга в круге, либо существует число c, такое что a и с являются непосредственными соседями, а также b и c являются непосредственными соседями. Нетрудно догадаться, что в итоге Вася нарисовал 2·n дуг.

Например, если числа по кругу написаны в порядке 1, 2, 3, 4, 5 (по часовой стрелке), то дугами будут соединены пары чисел (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4), (3, 5), (4, 1) и (5, 2).

С тех пор прошло немало времени, числа с доски были давно стерты, но не так давно Вася нашел у себя листочек с выписанными 2·n парами чисел, которые были соединены дугами на доске. Вася просит вас найти порядок чисел в круге по этим парам.

Входные данные

В первой строке входных данных записано единственное целое число n (5 ≤ n ≤ 105) — количество чисел в круге. Далее в 2·n строках даны пары целых чисел ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — числа, соединенные дугами.

Гарантируется, что никакая пара чисел, соединенных дугой, не задана во входных данных более одного раза. Пары и числа в парах заданы в произвольном порядке.

Выходные данные

Если Вася где-то ошибся, и не существует ни одного способа расположить числа от 1 до n на круге согласно условию, то выведите единственное число «-1» (без кавычек). Иначе выведите любую подходящую последовательность из n различных целых чисел от 1 до n.

Если существует несколько решений, то разрешается вывести любое. В частности, не имеет значения от какого числа начинать последовательность, описывающую порядок, также неважно по часовой стрелке выписывать числа или против.

Примеры
Входные данные
5
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2
Выходные данные
1 2 3 4 5
Входные данные
6
5 6
4 3
5 3
2 4
6 1
3 1
6 2
2 5
1 4
3 6
1 2
4 5
Выходные данные
1 2 4 5 3 6