TopCoder

Thumb square output jddoia
$\huge南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

22.7% (5/22)

Description

在某個神秘的島上有許多神秘的遺跡,這些遺跡會干擾 Geass 能力的使用,

不過還好這些遺跡都是藉由一種叫做櫻石(Sakura Dite)的神秘金屬才能發揮作用,

所以魔女C.C.可以利用一種叫做“豐饒女神干擾發射器”的裝置將遺跡之力給消除。

一座“豐饒女神干擾發射器”可以將安裝地點和其相鄰地點的遺跡之力消除掉,

然而,這種裝置是非常昂貴的,

為了能夠省錢吃到更多的pizza,C.C.必須慎選安裝地點。

告訴你遺跡的數量以及他們的相鄰位置關係,

你能算出至少要安裝幾座“豐饒女神干擾發射器”嗎?

Input Format

有多組測試資料。

每組測試資料開頭有兩個整數 N 跟 M,N≤50 且 M≤10000。

接著有 M 行,每行有兩個數字 (u,v),代表他們是相鄰的。

當 N=0 的時候代表測資結束。

Output Format

每組輸出一個數代表至少要安裝幾座“豐饒女神干擾發射器”。

Sample Input

8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
4 1
1 2
0 0

Sample Output

2
3

Hints

Problem Source

原TIOJ1381 / 快樂暑假營第二次練習比賽。Problem Setter:akira

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5
5 4000 65536 262144 6
6 4000 65536 262144 7
7 4000 65536 262144 8
8 4000 65536 262144 9
9 4000 65536 262144 10