#4375. Selling Tickets

内存限制:128 MiB 时间限制:20 Sec

题目描述

厨师在一次晚宴上准备了n道丰盛的菜肴,来自世界各地的m位顾客想要购买宴会的门票。每一位顾客都有两道特别喜爱的菜,而只要吃到了至少一道他喜爱的菜,这位顾客就会感到很高兴。当然,每道菜最多只能供应给一位顾客。厨师想要卖出尽可能多的门票,但同时要能够保证,无论哪些顾客购买门票,所有到来的顾客都能感到高兴。现在,厨师想要问你,他最多能够卖多少门票?

输入格式

输入的第一行包含一个正整数T,表示数据组数。
对于每组数据,第一行包含一对整数n和m,分别表示菜肴的数量与顾客的数量。接下来m行,第i行的两个正整数Ai, Bi代表第i位顾客喜爱的两道菜的编号。相邻的两组数据之间用一个空行分隔。

输出格式

输出总共T行,对于每组数据,输出一个整数,表示厨师最多能售出的门票数。

样例

样例输入


			
3
6 4
1 2
1 2
3 4
5 6

6 5
1 2
1 2
1 2
3 4
5 6

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

样例输出


			
4
2
4

数据范围与提示

对于第二组数据,厨师不能卖3张门票。因为如果顾客1, 2, 3购买门票,厨师是不可能用菜肴1, 2满足三个顾客的要求的。



【数据规模与约定】

1≤T≤15,   2≤n≤200,   0≤m≤500

1≤Ai, Bi≤n且Ai≠Bi