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

Уявімо, що на дошці записано деяку перестановку чисел від 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).