1978 . 邀請函（Invitation）
TopCoder
Tags
Description
古老的米克斯王國共住了 n 個米克斯人，每個米克斯人都有自己的住所，住所編號為 0, 1, …, n – 1，任兩位米克斯人的住所間可能有雙向的通道、也可能沒有通道（但不會只有單向的通道）。米克斯國王常常舉辦全國性會議，他希望越多人出席越好，但被邀請出席者一定要符合一個特殊規定，即若兩位米克斯人的住所間有通道，則其中至多只有一人會受到邀請。給定 n 與所有通道，下次舉辦全國性會議時，總共要印製幾張邀請函？
Input Format
測資的第一行為住所總數 n，n 為一正整數，且住所編號為 0, 1, …, n – 1。第二行是總通道數 m。接下來的 m 行中，每行有兩個正整數 i, j（以空白區隔），代表住所 i 與住所 j 之間有一通道。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $N\leq 24$ | 10 |
| 2 (0~9) | $N\leq 40$ | 25 |
| 3 (10~14) | $N\leq 80$為偶數，而且每條通道連接住所 {0, 1, …, n/2 – 1} 與 {n/2, n/2 + 1, …, n – 1} 各其中之一。 | 40 |
| 4 (0~22) | $N\leq 80$ | 25 |
Output Format
請輸出下次全國性會議舉辦時所需印製邀請卡數量。
Sample Input 1
6
6
0 3
1 5
3 2
2 5
0 4
1 0
6
0 3
1 5
3 2
2 5
0 4
1 0
Sample Output 1
3
Sample Input 2
7
8
6 5
0 3
2 6
3 5
1 4
1 2
3 4
2 3
8
6 5
0 3
2 6
3 5
1 4
1 2
3 4
2 3
Sample Output 2
4
Hints
經測試發現本處的測資較強。為了模擬模考時的難度，時限有作相應的放寬。
Problem Source
題目取自2017 TOI選訓第三次模擬考pD
Problem Set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 10 |
| 2 | 0~9 | 25 |
| 3 | 10~14 | 40 |
| 4 | 0~22 | 25 |