Смотровые площадки Ала-Арчи
В ущелье Ала-Арча оборудовали n смотровых площадок и m спусков между ними. Спуск i ведёт с площадки a[i] на площадку b[i], и подняться по нему обратно нельзя; так как каждый спуск ведёт вниз, по спускам невозможно вернуться на уже пройденную площадку.
Турклуб «Тенгри» хочет отправить несколько групп. Каждая группа начинает на любой площадке и идёт только по спускам, пока не решит остановиться. Нужно, чтобы каждая площадка была посещена хотя бы одной группой (группы могут проходить одни и те же площадки и спуски). Какое наименьшее число групп понадобится?
Входные данные
В первой строке — два целых числа n и m (1 ≤ n ≤ 1500, 0 ≤ m ≤ 10⁵). В каждой из следующих m строк — два различных числа a[i], b[i] (1 ≤ a[i], b[i] ≤ n). Гарантируется, что циклов нет.
Выходные данные
Выведите наименьшее количество групп.
Пример 1
Вход:
6 6
1 2
2 4
3 4
4 5
4 6
1 3
Выход:
2
Пояснение
На рисунке — площадки примера. Хватит двух групп: 1 → 2 → 4 → 5 и 3 → 4 → 6. Площадка 4 посещается обеими группами — так можно. Одной группы не хватит: площадки 5 и 6 нельзя посетить одной группой.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 15.
Подсказка
Теорема Дилуорса: наименьшее число цепей, покрывающих частично упорядоченное множество, равно наибольшему размеру антицепи.
Комментарии