← 返回题目
题库练习 多余的数据
← 上一题 下一题 →

A71367 | 多余的数据

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

我们都知道如果 x 和 y 属于同一个集合，y 和 z 属于同一个集合，那么 xyz 就属于同一个集合。

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

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

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

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

输入格式

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

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

1≤n,m≤1000，1≤x,y≤n 。

输出格式

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

输入输出样例

输入 #1
3 3
1 2
1 3
2 3
输出 #1
1
C++ 编辑器
输入
输出