冗余连边计数

难度：T2

【知识点：并查集】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

开始时有 $n$ 个顶点，编号为 $1$ 到 $n$，没有任何边。按输入顺序逐条加入边，判断一条边是否冗余时只考虑在它之前已经加入的边。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$。无向边的两个端点可互相通行。

输入$n$、$m$及按顺序加入的$m$条无向边。加入时若两端已连通，本条记为冗余；自环也计冗余。

输出格式

输出冗余边的总条数。

数据范围

$1\le n\le 100000$，$0\le m\le 200000$，端点在$1$..$n$。

样例输入

1 1
1 1

样例输出

1

样例输入 2

4 4
1 2
2 3
1 3
4 4

样例输出 2

2

样例说明 2

第三条边的两端已经连通，第四条是自环，因此共有两条冗余边。