TopCoder

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

50.0% (4/8)

Tags

Description

回到剛剛燈控的問題,你喜歡玩電燈,但只對一個電燈開開關關,是很無趣的。
比較有趣的玩法,應該是要一次玩兩個電燈才好玩,因為你有兩隻手嘛~
但是要一次玩兩個電燈是有難度的,比方說一個電燈在地心而另一個在月球上,這樣的兩個電燈是不可能同時玩的。
而且,對於玩過的電燈,你是不會再玩一次的,不然很蠢而且很無聊。

現在有N個電燈,還有M種可行的玩法,問你最多可以玩幾次?

Input Format

輸入的第一行有一個整數T,代表接下來有幾組測資。

每組測資的第一行有兩個整數N,M(N<=500,M<=20000),代表有N個電燈,有M種玩法。
接下來有M行,每行兩個數字x,y,代表編號x和編號y這兩個電燈是可以一起玩的,電燈的編號為0~N-1。

Output Format

對每組測資,輸出最多可以玩幾次。

Sample Input

2

12 13
11 1
1 3
1 2
2 3
2 4
4 6
2 6
2 5
5 7
7 2
7 8
8 9
8 10

3 2
1 2
2 0

Sample Output

5
1

Hints

Problem Source

原TIOJ1504 / problem setter: kelvin, seanwu

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1