Задачи
Перестановка
Перестановка
Уявімо, що на дошці записано деяку перестановку чисел від 1 до \textit{\textbf{N}}, а в Петриковому зошиті --- кілька впорядкованих пар чисел, причому кожне число в межах від \textit{\textbf{1}} до \textit{\textbf{N}} і числа в парі не можуть бути однаковими. Якщо на дошці поряд стоять два числа, які в тому ж порядку утворюють одну з пар у зошиті, будь-яке з цих двох чисел на дошці Петрик може витерти. При цьому Петрик вважає, що чи́сла, які розділяло витерте число, тепер стоять поряд.
\textbf{Завдання}
Напишіть програму permutation, що для заданого набору пар чисел, виписаних у Петриковому зошиті, будує приклад початкової перестановки чисел, яку хлопець зможе шляхом послідовних витирань звести до єдиного (довільного) числа, або встановлює, що такої перестановки не існує.
\InputFile
У першому рядку вхідного файла записано натуральні числа \textit{\textbf{N}} та \textit{\textbf{M}} (\textbf{2 ≤ N ≤ 10^\{5 \}}, \textbf{2 ≤ M ≤ 10^5} ), де \textit{\textbf{M}} --- кількість упорядкованих пар, записаних у зошиті Петрика. Наступні \textit{\textbf{M}} рядків містять по два числа --- елементи відповідних пар. Кожне число натуральне, не перевищує \textit{\textbf{N}} та відмінне від іншого числа в парі. Серед заданих упорядкованих пар немає однакових.
\OutputFile
У перший рядок вихідного файла слід вивести будь-який приклад перестановки чисел від \textit{\textbf{1}} до \textit{\textbf{N}}, яку Петрику вдасться звести до одного числа, а у другий рядок потрібно вивести послідовність з \textit{\textbf{N-1}} числа, які одне за одним витиратиме Петрик. У випадку, якщо потрібної перестановки не існує, у вихідний файл треба вивести єдине число 0.
\Scoring
Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:
1. 20 \% балів: 2 ≤ N ≤ 5.
2. 35 \% балів: 5 < N ≤ 1000.
3. 45 \% балів: 1000 < N ≤ 10^5.
\textbf{Пояснення. }У перестановці 1 3 4 2 можемо витерти трійку, бо маємо пару 3 4. Далі послідовність чисел на дошці стає такою: 1 4 2. Тепер можемо витерти четвірку, бо маємо пару 1 4. На дошці залишається пара чисел 1 2. Оскільки ця пара також є в Петриковому зошиті, можемо витерти, наприклад, одиницю, залишивши на дошці єдине число (в даному випадку --- 2).
Входные данные #1
4 4 1 4 4 3 1 2 3 4
Выходные данные #1
1