ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Лето — 2022» > задача:


J. Макс и зачёты

Тренировочный турнир сезона «Лето — 2022»

Старт: 01.июня.2022 в 14:00:00
Финиш: 31.авг.2022 в 23:00:00
Осталось: 363:48:22
• Турнирная таблица

Задачи турнира

• B. Макс и солдатики
• C. Макс и продажа кристаллов
• D. Турнир по Hearthstone
• E. Макс и судоку
• F. Макс и e-mail
• G. Макс и кормушка для птиц
• H. Макс и купюры
• I. Макс и чтение
• J. Макс и зачёты
• K. Макс и аквариумистика
• L. Автоформатирование
• M. Макс и продажа кристаллов
• N. Макс и доллары
• O. Макс и невзламываемый пароль
• P. Макс и лотерея
• Q. Макс и розы
• R. Макс и сериал

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/3000/3000/3000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и зачёты
Макс и зачёты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Входные данные

Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 20$$$, $$$0 \le M \le N \cdot (N - 1)$$$) — соответственно количество зачётов и количество взаимосвязей между ними.

Следующие $$$M$$$ строк описывают взаимосвязи между зачётами. Каждая из них содержит целые числа $$$A_i$$$ и $$$B_i$$$ ($$$1 \le A_i, B_i \le N$$$) — соответственно номер зачёта, который нужно сдать, и номер зачёта, который после этого будет получен автоматом.

Выходные данные

Выведите одно целое число — минимальное количество зачётов, которые нужно сдать Максу, чтобы закрыть сессию.

Примеры

Входные данные
3 2
1 2
2 3
Выходные данные
2
Входные данные
3 2
1 2
1 3
Выходные данные
1

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

www.contester.ru