```

Time Limit: 1000 MS    Memory Limit: 65536 K

Description

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.

Input

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.

Output

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

2

Hint
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.

Author
zsasuke

Source

Sichuan University Programming Contest 2011 Preliminary

```