TopCoder

User's AC Ratio

70.0% (7/10)

Submission's AC Ratio

52.6% (10/19)

Tags

Description

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

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

Input Format

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

每組測資的第一行有兩個整數$N,M$($N\leq 500, M\leq 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
$\LaTeX$ fixed by Seanliu on 20210316

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