1253 . 砲打皮皮
TopCoder
Description
皮皮是一種在『皮皮歷險記』中隨處可見，強度約等於一般RPG中史萊姆的怪物，但皮皮卻有一個神奇的特性，就是任何武器都無法消滅他，唯一能打敗他的只有從這個到處充滿著強者的空間中提煉出來的的強者物質。
『皮皮歷險記』中第一個關卡就是『砲打皮皮』，遊戲的畫面是由一個NxN的棋盤所構成，但是在某些的格子上有著弱小的皮皮，而你必須要消滅所有皮皮才能通過這塊區域。故事中強大的永日製造了一把很威的槍，可以將一單位強者物質發射出去，並且消滅一整行或一整列的皮皮，請問你至少需要多少單位的強者物質，才能消滅棋盤上所有的皮皮？
Input Format
輸入可能包含多筆測試資料。
每筆測試資料的第一行有兩個正整數N, K，表示棋盤大小和皮皮的數量
（1 ≦ N ≦ 1,000，1 ≦K ≦ 20,000）。
接下來K行，每行有兩個數R和C，代表一隻皮皮的位置（1 ≦ R, C ≦ N）。
當N = K = 0時，代表輸入結束，聰明的你當然不會對它輸出任何資料。
Output Format
請先輸出"Case #N:"表示這是第N筆輸出。
接著輸出至少需要多少強者物質。
Sample Input 1
3 4
1 1
1 3
2 2
3 2
0 0
1 1
1 3
2 2
3 2
0 0
Sample Output 1
Case #1:2
Hints
地圖如下：（ "X"表示一隻皮皮，"."表示空白）
X.X
.X.
.X.
Problem Source
原TIOJ1253 / INFOR 21st幹部考(prob I)。Problem Setter：peter50216。
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 |