1381 . C.C.と桜石
TopCoder
Tags
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 1
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
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 1
2
3
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 |