5846 - GESP:2025-6月等级7-T1-线图

通过次数

1

提交次数

1

Time Limit : 1 秒
Memory Limit : 128 MB

给定由 n 个结点与 m 条边构成的简单无向图 G,结点依次以 1,2,…,n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建:

(1).初始时线图 L(G) 为空。 (2).对于无向图 G 中的一条边,在线图 L(G) 中加入与之对应的一个结点。 (3).对于无向图 G 中两条不同的边 (u1,v1),(u2,v2),若存在 G 中的结点同时连接这两条边(即 u1,v1 之一与 u2,v2 之一相同),则在线图 L(G) 中加入一条无向边,连接 (u1,v1),(u2,v2) 在线图中对应的结点。 请你求出线图 L(G) 中所包含的无向边的数量。

Input

第一行,两个正整数 n,m,分别表示无向图 G 中的结点数与边数。

接下来 m 行,每行两个正整数 ui,vi,表示 G 中连接 ui,vi 的一条无向边。

Output

输出共一行,一个整数,表示线图 L(G) 中所包含的无向边的数量。

Examples

Input

5 4
1 2
2 3
3 1
4 5

Output

3

Input

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Output

30

Hint

样例1解释 对于 60% 的测试点,保证 1≤n≤500,1≤m≤500。 对于所有测试点,保证 1≤n≤10^5,1≤m≤10^5。