TopCoder

User's AC Ratio

68.4% (13/19)

Submission's AC Ratio

23.6% (57/242)

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

#Sample Input 1
6
6
0 3
1 5
3 2
2 5
0 4
1 0
#Sample Input 2
7
8
6 5
0 3
2 6
3 5
1 4
1 2
3 4
2 3

Sample Output

#Sample Output 1
3
#Sample Output 2
4

Hints

經測試發現本處的測資較強。為了模擬模考時的難度,時限有作相應的放寬。

Problem Source

題目取自2017 TOI選訓第三次模擬考pD
Problem Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 4, Score: 10
For Testdata: 0 ~ 9, Score: 25
For Testdata: 10 ~ 14, Score: 40
For Testdata: 0 ~ 22, Score: 25
No. Time Limit (ms) Memory Limit (KiB)
0 1900 262144
1 1900 262144
2 1900 262144
3 1900 262144
4 1900 262144
5 1900 262144
6 1900 262144
7 1900 262144
8 1900 262144
9 1900 262144
10 1900 262144
11 1900 262144
12 1900 262144
13 1900 262144
14 1900 262144
15 2900 262144
16 1900 262144
17 2900 262144
18 1900 262144
19 1900 262144
20 2900 262144
21 2900 262144
22 2900 262144