EduBrick

N. Сколько компонент — деревья

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

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

Компонента — дерево, если в ней рёбер ровно на одно меньше, чем вершин. Считать рёбра компоненты надо аккуратно: каждое ребро принадлежит ровно одной компоненте, петли и кратные рёбра тоже считаются.

Формат ввода

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

Далее идут mm строк с рёбрами. Возможны петли и кратные рёбра.

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

Одно число — количество компонент, являющихся деревьями.

Примеры

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