eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Домино

Домино

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

По заданной расстановке домино необходимо определить, какое минимальное их количество необходимо толкнуть рукой, чтобы все домино упали.

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

Первая строка содержит два числа, каждое из которых не более 10^5. Первым является количество костяшек домино n, а вторым – количество строк m, которое идет дальше в этом тесте. Кости домино пронумерованы числами от 1 до n. Каждая из следующих строк содержит два числа x и y, обозначающих тот факт, что если домино x упадет, то оно собьет домино y.

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

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

prb1104.gif

Пример

Входные данные #1
3 2
1 2
2 3
Выходные данные #1
1
Входные данные #2
5 5
2 3
1 2
4 2
5 3
5 4
Выходные данные #2
2
Источник Летняя Школа 2010, Севастополь, день М.Медведева