У першому рядку вхідного файла записано натуральні числа 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).