Вася написал на доске по кругу в некотором порядке 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 парами чисел, которые были соединены дугами на доске. Вася просит вас найти порядок чисел в круге по этим парам.
Выходные данные
Если Вася где-то ошибся, и не существует ни одного способа расположить числа от 1 до n на круге согласно условию, то выведите единственное число «-1» (без кавычек). Иначе выведите любую подходящую последовательность из n различных целых чисел от 1 до n.
Если существует несколько решений, то разрешается вывести любое. В частности, не имеет значения от какого числа начинать последовательность, описывающую порядок, также неважно по часовой стрелке выписывать числа или против.