Перестановка

Представьте, что на доске записана некоторая перестановка чисел от 1 до N, а в тетрадке Петрика содержатся несколько упорядоченных пар чисел. Каждое число в этих парах находится в диапазоне от 1 до N, и числа в паре не могут совпадать. Если на доске рядом стоят два числа, которые в том же порядке образуют одну из пар из тетрадки, Петрик может стереть любое из этих двух чисел. При этом он считает, что числа, которые разделяло стёртое число, теперь стоят рядом.

Задача

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

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

В первой строке входного файла указаны натуральные числа N и M (2 ≤ N ≤ 10^{5 }, 2 ≤ M ≤ 10^5), где M — количество упорядоченных пар в тетрадке Петрика. Следующие M строк содержат по два числа — элементы каждой пары. Каждое число натуральное, не превышает N и отличается от другого числа в паре. Среди заданных пар нет одинаковых.

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

В первой строке выходного файла необходимо вывести любой пример перестановки чисел от 1 до N, которую Петрик сможет свести к одному числу. Во второй строке нужно вывести последовательность из N-1 чисел, которые Петрик будет стирать по порядку. Если такой перестановки не существует, выведите единственное число 0.

Примеры

Оценивание

Набор тестов состоит из 3 блоков, для которых дополнительно выполняются следующие условия:

1. 20 % баллов: 2 ≤ N ≤ 5.

2. 35 % баллов: 5 < N ≤ 1000.

3. 45 % баллов: 1000 < N ≤ 10^5.

Пояснение. В перестановке 1 3 4 2 можно стереть тройку, так как существует пара 3 4. Далее последовательность на доске становится: 1 4 2. Теперь можно стереть четверку, так как есть пара 1 4. На доске остаётся пара чисел 1 2. Поскольку эта пара также есть в тетрадке Петрика, можно стереть, например, единицу, оставив на доске единственное число (в данном случае — 2).