Задача A. Бюрократия ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4 3
1 2
1 3
3 4

1 3 2 4

Задача B. Перестройка ≡

Условие

В некоторой стране было ровно N городов и M дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:

• между любыми двумя городами не больше одной дороги;
• никакая дорога не соединяет город с самим собой.

После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:

• разрушить одну из существующих дорог;
• построить новую дорогу, которой раньше не было, не ведущую из города в него же.

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

Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.

Формат входного файла

Первая строка содержит два целых числа N и M. Следующие M строк содержат два числа a_i, b_i  — номера городов, которые соединяет i-я дорога.

Формат выходного файла

Выведите одно целое число  — количество способов провести реформу.

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ M ≤ 2 ⋅ 10⁵

1 ≤ a_i, b_i ≤ N, a_i ≠ b_i

Problem C. Eulerian cycle ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2
2 3
3 1

1 2 3 1

Задача D. Breadth First Search ≡

Условие

Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S. Расстояние между вершинами A и B это длина кратчайшего пути из A в B. Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S, выведите их в произвольном порядке.

Формат входного файла

Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины. Вершины пронумерованы целыми числами от 1 до N. Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.

Формат выходного файла

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

Ограничения

Примеры тестов

3 2 1
1 2
2 3

1 2 3