2427 - 多余的数据

题目描述

我们都知道如果 xy 属于同一个集合,yz 属于同一个集合,那么 xyz 就属于同一个集合。

A 同学发现一组关于集合关系的描述中经常出现多余的数据,比如,以下数据中,每行的 2 个整数 x y,代表了 xy 属于同一个集合:

1 2
2 3
3 4
1 3
1 4
2 4

观察发现,只要有前 3 个关系,就可以断定 1 2 3 44 个数属于同一个集合,后面的 3 个关系是多余的数据。

现有 n 个数,数值为 1 \sim n,有 m 个关系,描述了哪些数在同一个集合,请编程计算出,这些关系中,有多少个关系是多余的?

输入

第一行,读入两个整数,分别表示:关系数量(m)和人数(n)。

接下来 m 行,每行两个数 x y,表示 xy 在同一个集合中。

1≤n,m≤10001≤x,y≤n

输出

输出一个整数,表示有多少个关系是多余的。

样例

输入

3 3
1 2
1 3
2 3

输出

1
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题