Time Limit: 1000 MS    Memory Limit: 65536 K 


As a leader,LiuBang has many excellent generals as his subordinates,Such as Hanxin,YingBu,PengYue,JiBu,FanKuai and so on. After LiuBang unified China,he divided his territory into n different regions and decided to send these generals out to govern them. It is common sence that one general can at most govern one region and one region can be governed by at most one general. There exist some bidirectional roads between some regions, and for any two distinct regions, at most one road exists between them. there is no self-loop,that is to say, the structure of the regions and the roads connecting them forms a simple graph. Besides, for any two adjacent regions (a road connects them)A and B, there are at most two different simple routes from A to B(Hint:simple route contains no duplicate regions or roads) It is rumored that if there are two adjacent regions are both being governed by these generals, the two generals who govern them will plot to rebel, LiuBang could not tolerate such situation completely. But it is also believed the more generals he send out to govern these regions, the more stable his country will be. Now LiuBang wants to know, how many generals he can send out at most while guaranteeing no rebellion would happen.


The first line of the input contains an integer T indicating the number of cases. Each case contains two positive integers n,m (1 <= n <= 10000,1 <= m <= 20000 ), in the first line, indicating the number of regions and the number of roads. then m lines follow, each line contains 2 positive integers A,B(1 <= A,B <= n,A!=B) indicating a road connecting region A and region B.


a single Integer for each case indicating the maximun number of generals LiuBang could send out.

Sample Input

1 4 2 1 2 3 4

Sample Output



LiuBang Can send two generals to 1 and 3,but if LiuBang send the two generals to 1 and 2,they will plot to rebel as region 1 and 2 are adjacent.




Sichuan University Programming Contest 2011 Preliminary