几队周尼玛?

发布时间: 2017年6月19日 00:22   最后更新: 2017年6月20日 04:13   时间限制: 1000ms   内存限制: 128M

超级无敌张小豪是A国的一名勇士,A国的勇士都要靠获得能量变得更强,在A国勇士获得能量只有唯一的一种途径就是膜拜宙斯神——周尼玛(桑!!!)。要膜拜周尼玛就要去到遥远的大日国那里有好多好多周尼玛(桑!!!)。但是周尼玛(桑!!!)是一种群居动物,一队周尼玛(桑!!!)中都有且只有一个领袖叫周尼玛你妹(桑!!!)超级无敌张小豪勇士必须拿着一炷香到周尼玛你妹(桑!!!)面前膜拜三下即可获得一点能量。

膜拜必须遵循一些规则:

对于一个周尼玛你妹(桑!!!)只能膜拜一次;

不能膜拜周尼玛(桑!!!);

一次膜拜用一炷香且一炷香只能膜拜一次;

现在问题出现了,小豪准备启程去大日国,在走之前小豪要准备买香但是小豪不知道大日国一共有几队周尼玛(桑!!!),小豪既想每个周尼玛你妹(桑!!!)都膜拜到,又想带过去的香能用完不浪费。于是小豪打听小道消息搞过来了一张周尼玛(桑!!!)家族谱。

家族谱上有若干对数字

eg:1 2

    2 4

表示:周尼玛1号和周尼玛2号是一队的

      周尼玛2号和周尼玛4号是一队的

若谱上告诉你周尼玛x号和周尼玛y号是一队的周尼玛y号和周尼玛z号是一队的

那也就代表了周尼玛x号和周尼玛z号是一队的了。

The input starts with an integer T(1<=T<=10) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N<= 30000,1<=M<= 500000). N indicates the number of 周尼玛, the 周尼玛 are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means 周尼玛 A and 周尼玛 B in the same team. There will be a blank line between two cases.

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks. 

复制
2
5 3
1 2
2 3
4 5
5 1
2 5
2
4

1537

data structure

无敌张小豪