Тема: Обходы графов


A. Слияние множеств
ограничение по времени на тест
2 секундыограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводИмеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.

Вам нужно выполнить M запросов. В каждом запросе даются целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если они уже в одном множестве, то ничего не делать).


Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).

В следующих M строках записаны по два целых числа – номера объектов, множества которых нужно объединить.

Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.
Пример
входные данные
6 5
1 2
3 4
6 5
2 3
3 1
выходные данные
2
Примечание
В примере останутся два множества – {1, 2, 3, 4} и {5, 6}.

B. Объединения с отменами
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводИмеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.

Вам нужно выполнить M запросов двух типов.

Первый тип запроса – объединение двух множеств. Вам даются два целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если объекты уже в одном множестве, то ничего делать не нужно).

Второй тип запроса – отмена последнего выполненного запроса на объединение. Учитываются и те запросы, в которых реального объединения не происходило (при отмене таких запросов также делать ничего не надо).


Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).

В каждой из следующих M строк записаны по два целых числа u и v. Если u > 0, v > 0, то это запрос первого типа, и вам нужно выполнить объединение множеств, содержащих эти элементы. Если же u = v = 0, то это запрос второго типа, и нужно выполнить отмену последнего выполненного запроса на объединение.

Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.

Примеры
входные данныеСкопировать
6 7
1 2
3 4
2 3
0 0
0 0
3 5
1 3
выходные данные
3
входные данные
3 5
1 2
2 3
3 1
0 0
0 0
выходные данные
2
Примечание
В первом примере останутся три множества – {1,2,3,5}, {4} и {6}.

Во втором примере останутся два множества – {1,2} и {3}.


C. Михаил Густокашин против бюрократии
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводЗадача классическая. Формулировка: Михаил Густокашин.

Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.

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

Закончилось тем, что я составил список, какому врачу нужны какие справки.


Входные данные
В первой строке моего списка содержится общее количество врачей (1 ≤ K ≤ 100). В следующих K строках описываются необходимые справки. Первое число (j) в i + 1 строке входных данных означает, сколько справок нужно i-му врачу. Затем, в той же строке, содержится j чисел – номера врачей, чьи подписи надо предварительно поставить, чтобы получить подпись i-го врача.

Выходные данные
Если подписи всех врачей собрать невозможно, то следует вывести "NO". Если же все справки собрать возможно, то в первой строке должно содержаться "YES", а в следующих K строках – последовательность, в которой нужно получать справки.

Пример
входные данные
4
1 2
0
2 1 4
1 1
выходные данные
YES
2
1
4
3





Тема: Кратчайшие пути в графах



C. Цикл
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводДан взвешенный ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.


Входные данные
В первой строке входных данных записано число N (1 ≤ N ≤ 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

Выходные данные
Выведите "YES", если цикл существует, и "NO" в противном случае.
Пример
входные данные
2
0 -1
-1 0
выходные данные
YES
D. Автобусы
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводМежду некоторыми деревнями Пермской области ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день (например, в Ляды из Перми автобус приходит лишь 3 раза в сутки).

Ирине Владимировне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).


Входные данные
Во входных данных записано число N – общее число деревень (1 ≤ N ≤ 100), затем деревни d и v, затем количество автобусных рейсов R (0 ≤ R ≤ 10000).

Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000).

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

Выходные данные
Выведите минимальное время, когда пассажир может оказаться в деревне v. Если он не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.
Пример
входные данные
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
выходные данные
5