eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Уявімо, що на дошці записано деяку перестановку чисел від 1 до N, а в Петриковому зошиті — кілька впорядкованих пар чисел, причому кожне число в межах від 1 до N і числа в парі не можуть бути однаковими. Якщо на дошці поряд стоять два числа, які в тому ж порядку утворюють одну з пар у зошиті, будь-яке з цих двох чисел на дошці Петрик може витерти. При цьому Петрик вважає, що чи́сла, які розділяло витерте число, тепер стоять поряд.

Завдання

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

Giriş verilənləri

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

Çıxış verilənləri

У перший рядок вихідного файла слід вивести будь-який приклад перестановки чисел від 1 до N, яку Петрику вдасться звести до одного числа, а у другий рядок потрібно вивести послідовність з N-1 числа, які одне за одним витиратиме Петрик. У випадку, якщо потрібної перестановки не існує, у вихідний файл треба вивести єдине число 0.

Nümunə

Giriş verilənləri #1
4 4
1 4
4 3
1 2
3 4
Çıxış verilənləri #1
1

Qiymətləndirmə

Набір тестів складається з 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).

Mənbə XXVIII Всеукраїнська олімпіада з інформатики 2015 р.