| Автор: | М. Спорышев | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая скажет, существует ли способ получить справки от всех чиновников
Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".
YES, если существует способ собрать все справки и NO в противном случае.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | |
|---|---|---|---|---|
| N | M | |||
| 1 | 25 | 1 ≤ N ≤ 100 | 1 ≤ M ≤ 100 | |
| 2 | 15 | 1 ≤ N ≤ 103 | 1 ≤ M ≤ 104 | 1 |
| 3 | 20 | 1 ≤ N ≤ 104 | 1 ≤ M ≤ 105 | 1,2 |
| 4 | 40 | 1 ≤ N ≤ 105 | 1 ≤ M ≤ 105 | 1,2,3 |
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|