EduBrick

B. Сколько достижимо

3000 мс · 256 МБ · всё или ничего

Ориентированный граф задан списком рёбер. Посчитайте, сколько вершин достижимо из вершины 1, считая её саму.

Обход в глубину годится и для ориентированного графа: разница лишь в том, что ребро добавляется в список смежности только одного конца.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с парами (u,v)(u, v) — ребро ведёт из uu в vv. Возможны петли и кратные рёбра.

Формат вывода

Одно число — количество достижимых вершин.

Примеры

ввод
4 3
1 2
2 3
4 1
вывод
3
ввод
3 2
2 1
3 1
вывод
1
Войдите, чтобы отправлять решения.