TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

78.7% (48/61)

Submission's AC Ratio

26.0% (120/461)

Tags

Description

當一名騎士是非常令人嚮往的職業:尋找聖杯、拯救落難女子、跟其他騎士共飲皆是十分有趣的事情。

自然,毫不令人感到意外地,近幾年亞瑟王的王國內騎士人數出現了空前的大幅成長。

由於騎士的人數實在是太多了,他們也很少有機會能召集所有圓桌武士到卡默洛並且一同坐在圓桌周圍了。

通常只有一小部份的騎士會在那裡,剩下的則都散布全國各地忙於作一些英雄事蹟。

騎士們很容易在會談中激動起來--尤其在一兩杯黃湯下肚後。

在經過一些不開心的意外後,亞瑟王請求梅林法師想一個方案確保以後不會再發生騎士之間的爭鬥。

梅林深入瞭解這個事件後發現如果遵守下面兩條規則,爭吵將不再發生:

※兩位相互憎恨的騎士不能在坐在圓桌的相鄰位置(梅林有一張關於誰憎恨著誰的表格)。

 所有騎士都坐在圓周周圍,亦即每個騎士都會有恰好兩個相鄰的騎士。


※圓桌上的騎士總數必須是個奇數:這保證了當他們沒有共識時可以進行投票表決。

 (如果總數是偶數,可能發生正反方同票的悲劇,並且兩方持續爭吵)。

只有在上述兩個規則都符合時梅林才會讓那些騎士坐下,否則他會取消這次會面。

(如果總人數只有一人時,梅林也會取消會面--僅一個人是不可能坐在圓周四周(around a table)的)。

梅林瞭解到這樣的話會有些騎士永遠不可能在任何一場合法會面出席,表示他們永遠沒有機會坐在圓桌旁。

(例如說假設有一個騎士憎恨所有其他騎士--但是這僅僅是許多可能中的一種)。

如果一個騎士永遠沒機會坐在圓桌旁,那麼他就不能成為圓桌武士的一分子,必須從名單內除名。

他們會被派送到一些較低聲望的組織,例如方桌武士、八角武士、香蕉武士之類。

(the Knights of the Square Table, the Knights of the Octagonal Table, the Knights of the Banana-Shaped Table).

為了協助梅林,你必須寫一個程式算出有幾位騎士必須被除名。

Input Format

單一檔案包含多筆測資。

每筆測資第一行會有兩個整數1 ≤ n ≤ 1000以及1 ≤ m ≤ 1000000。

接下來的m行每行包含兩個數字k1 k2,表示k1跟k2互相憎恨。

(k1和k2都會是1~n之間的正整數)。

當n = m = 0時,輸入結束。

Output Format

對每筆測資輸出一行包含一個數字表示必須被除名的騎士總數。

Sample Input 1

5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output 1

2

Hints

輸入檔有點大,請使用較快速的I/O函式。

話說,香蕉桌是原題目的敘述XD

Problem Source

原TIOJ1684 / ACM-ICPC Central Europe 2005 prob A, POJ 2942

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1