Задача A. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача B. Радиус дерева ≡

Условие

Деревом называется связный неориентированный граф без циклов. Для заданного дерева требуется найти радиус.

Напишите программу, принимающую описание дерева и выводящую радиус дерева.

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

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа u_i v_i — номера вершин, которые соединены этим ребром.

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

Выходной файл должен содержать единственное целое число — радиус дерева.

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ u_i, v_i ≤ N.

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

2
1 2

1

3
1 2
1 3

1

7
1 4
2 3
2 4
2 5
4 6
4 7

2

Задача C. Расстояние от корня ≡

Условие

В заданном корневом дереве найдите вершины, максимально удалённые от корня. Расстоянием между вершинами считается количество рёбер в пути.

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

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, …, n. Вершина 1 является корнем дерева.

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

В первой строке выведите максимальное расстояние от корня до остальных вершин дерева.

Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии.

В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

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

3
1
1

1
2
2 3

3
1
2

2
1
3

Задача D. Листовая медиана ≡

Условие

Деревом называется связный неориентированный граф без циклов. Для заданного дерева требуется выбрать такую вершину, чтобы суммарное расстояние от неё до всех листьев было максимальным.

Напишите программу, принимающую описание дерева и выводящую вершину с максимальным суммарным расстоянием до листьев. Если таких вершин несколько, выведите минимальную по номеру.

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

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа u_i v_i — номера вершин, которые соединены этим ребром.

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

Выходной файл должен содержать единственное целое число — номер искомой вершины.

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ u_i, v_i ≤ N.

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

2
1 2

1

3
1 2
1 3

1

7
1 4
2 3
2 4
2 5
4 6
4 7

3

Задача E. Три пути ≡

Условие

Цапля вилка недавно переехала в Антарктику в государство пингвинов — Пингвинию, и устроилась работать в местную логистическую компанию. Всего в Пингвинии N городов и M дорог, по дорогам можно двигаться в обе стороны. Исторически сложилось, что каждый пингвин посещает ровно три города (возможно проезжая по пути через остальные города). Пингвины не любят однообразие, поэтому одна из самых популярных услуг в логистической компании это прокладка маршрутов между тремя городами a, b, c так чтобы при проезде из a в b, из a в c, и из b в с существовал максимум один город который посещался 3 раза.

Как вы уже могли догадаться Цапля просит вас о помощи, у неё скопилось ровно Q запросов вида a, b, c. И для каждого запроса требуется вывести 3 пути, из a в b, из a в c, и из b в c, так чтобы эти пути удовлетворяли заданным требованиям.

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

Входной файл содержит числа N и M. Далее следует M пар чисел u_i и v_i, означающих что города u_i и v_i соединены дорогой. Далее следует число Q, за которым следует Q попарно различных чисел a_i, b_i, c_i.

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

Выходной файл должен содержать 3 × Q строк, первое число в строке k_i — количество вершин в пути, далее k_i чисел — номера вершин пути в порядке посещения.

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000, 1 ≤ M ≤ N ⋅ (N − 1)2, 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ a_i, b_i, c_i ≤ N

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

3 2
1 2
2 3
1
1 2 3

2 1 2
3 1 2 3
2 2 3

4 3
1 2
1 3
1 4
2
3 4 1
1 2 4 

3 3 1 4 
2 3 1 
2 4 1 
2 1 2 
2 1 4 
3 2 1 4 

5 6
2 3
4 5
1 2
1 3
1 4
1 5
2
2 3 4
2 3 5

2 2 3 
3 2 1 4 
4 3 2 1 4 
2 2 3 
4 2 1 4 5 
5 3 2 1 4 5 

Задача F. Удлинители ≡

Условие

В компьютерном классе имеется одна розетка. Для того, чтобы подключить к ней компьютеры, используется N + 1 удлинителей. Один из удлинителей включается розетку, а каждый из остальных N — в другой удлинитель. При этом гарантируется, что каждый удлинитель в конце концов подключен к розетке.

В каждом удлинителе имеется K разъёмов, так что к нему можно подключить не более K других удлинителей.

Назовём электрическим расстоянием от удлинителя до розетки количество удлинителей, которые должен пройти электрический ток от данного удлинителя до розетки.

Такой способ организации электрической сети является очень ненадёжным. Особенно подвержены сбоям удлинители, электрическое расстояние от которых до розетки велико.

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

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

Входной файла содержит целые числа N K, за которыми следуют N чисел p_i, где p_i — номер удлинителя, к которому подключен i-й удлинитель, i = 1… N. К розетке подключен удлинитель номер 0.

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

Выходной файл должен содержать два целых числа S T, означающие, что удлинитель номер S следует отключить от удлинителя номер p_S и подключить к удлинителю номер T. Если оптимальных решений несколько, выведите любое из них.

Ограничения

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

6 2
0 1 2 1 6 0

3 6

1 5
0

1 0