EduBrick

C. Слабые компоненты

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

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

Обратите внимание: сильная связность, где важно, что дойти можно в обе стороны, — совсем другая история, и она будет позже.

Формат ввода

Первая строка содержит числа 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).

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

Одно число — количество компонент слабой связности.

Примеры

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