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

Условие

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

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

В первой строке входного файла заданы через пробел два целых числа 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

Задача 11. Элемент N-мерного масcива ≡

Условие

Требуется написать программу, которая по количеству измерений массива — N, размерностям измерений — a_i и индексы элемента в массиве — k_i, напечатает позицию элемента в памяти относительно начала массива. Размер элемента массива составляет один байт.

Формат входных данных

В первой строке входные данные содержат число N — количество измерений массива.

В следующих двух строках содержатся по N чисел a_i и k_i соответственно.

Формат выходных данных

Выходные данные должны содержать одно целое число — позицию элемента в памяти.

Ограничения

1 ≤ N ≤ 32

1 ≤ ∏a_i ≤ 2³²

0 ≤ k_i < a_i

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

1
10
8

8

2
2 5
1 3

8

2
5 5
2 1

11

Задача 2. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

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

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

3
1
1

1
2
2 3

3
1
2

2
1
3

Задача 4. Семь колонн Владивостока ≡

Условие

Когда абитуриент Дима пришёл в кампус ДВФУ на день открытых дверей, его внимание привлекла инсталляция "Семь колонн Владивостока".

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

Каждому объекту данной скульптурной группы соответствует одна из семи самых высоких сопок города Владивостока. Высоты объектов, а также расстояния между объектами пропорциональны реальным высотам и расстояниям. На вершине каждого объекта находится фрагмент породы соответствующей сопки. Высоты выполнены в масштабе 1:75, расстояния между объектами соответственно 1:100.

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

Дима знает, как посчитать число граней этого планарного графа, для этого нужно применить формулу Эйлера V − E + F = 2, где V — число вершин, E — число рёбер, F — число граней, включая внешнюю грань. В нашем случае V = 7, E = 13, отсюда F = 8, поэтому треугольных граней всего 7, что легко проверить.

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

Напишите программу, принимающую на вход данный граф и вычисляющую количество элементарных циклов в этом графе.

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

Входной файл содержит целые числа N M — количество вершин и количество рёбер соответственно. Далее следуют M пар целых чисел — рёбра графа.

Ребро не может идти из вершины в неё саму. В графе нет повторяющихся рёбер. Ребра (u, v) и (v, u) — это одно и то же ребро.

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

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

Ограничения

2 ≤ N ≤ 7

M ≥ 1

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

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

56

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

2

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

7

Задача 5. Репликация ≡

Условие

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

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

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

Рекомендуется рассмотреть частичные решения

• N ≤ 100

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

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

Ограничения

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

3 3
1 2
1 2
2 3

2
1
0

3 3
1 2
1 3
2 3

1
2
1

Задача K. Свинья-копилка ≡

Условие

Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела. Как известно, количество денег в копилке можно определить, только разбив ее. Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

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

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — C_i W_i. Все числа во входном файле — целые.

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

В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число  − 1.

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

10 110 2
1 1
30 50

60

10 110 2
1 1
50 30

100

1 6 2
10 3
20 4

-1