1372 . 黑色騎士團的第一野望
TopCoder
Tags
Description
要迅速攻佔大不列顛帝國，他們想到一個快又有效的辦法。
就是佔據一些道路，使得道路相連的城市，都可以在他的控制之下。
翻開大不列顛帝國的國土，你要找出黑色騎士團最少需要攻佔多少條道路
並將結果報告回司令部，好讓司令部擬出對策，打破黑色騎士團的野望
Input Format
本題有多筆測試資料，請以EOF作為結束。(測試資料不超過十組)
第一行為兩個數字，n，m分別代表有幾個城市，幾條道路
(0≦n≦50，0≦m≦25)
接著有m行，每行兩個數字，st，ed分別代表道路兩端連結的城市編號。
(0≦st，ed≦n-1)
Output Format
輸出黑色騎士團完成野望需要攻佔多少條道路。
如果黑色騎士團無法完成野望則輸出-1。
Sample Input 1
5 5
0 4
1 2
1 4
2 4
4 3
0 4
1 2
1 4
2 4
4 3
Sample Output 1
3
Hints
※2008/07/18 INPUT漏字修正 by hallogameboy。 感謝 SKYLY。
Problem Source
原TIOJ1372 / 快樂暑假營第二次練習比賽。
(最小邊覆蓋) Problem Setter：ggm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |