Условие:
Реями и её друзья
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Реями очень любила устраивать весёлые праздники для своих друзей. Однажды она решила собрать всех своих n
друзей за волшебным столом, который точно вмещал n
человек. Но не всё было так просто: среди её друзей были особые пары, которые давно дружили между собой. Всего было m
пар.
Реями захотела рассадить всех за столом так, чтобы каждая пара давних друзей сидела за соседними местами. За волшебным столом можно сидеть только с одной стороны.
Пример волшебного стола. Зеленым цветом показаны соседние места для синего места.
Теперь перед вами стоит задача помочь Реями: можно ли рассадить всех её друзей за волшебным столом так, чтобы каждая пара давних друзей сидела по соседству? Если это возможно, покажите, как это можно сделать.
Входные данные
В первой строке входных данных содержится два натуральных числа n
и m
(2≤n,m≤1000
) — число друзей Реями и количество пар давних друзей.
Во следующих m
строках содержится по два числа u
и v
(1≤u,v≤n
, u≠v
) — номера друзей, которые хотят сидеть рядом.
Гарантируется, что все пары (u,v)
различны.
Выходные данные
В единственной строке выходных данных выведите n
чисел p1,...,pn
— номера мест, на которых должны сидеть её друзья (друг под номером i
будет сидеть на pi
месте), если друзей возможно рассадить с пожеланиями Реями, и −1
иначе.