TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯,道歉!$

User's AC Ratio

90.3% (149/165)

Submission's AC Ratio

31.2% (298/954)

Tags

Description

Mimi, Moumou兩人是青梅竹馬,從小就玩在一起(雖然他們現在也才小學三年級而已)。愛玩的兩人,平常的遊戲玩久了之後就覺得無聊沒勁,常常湊在一起發明新的遊戲。

這天他們又開始在設計新遊戲了,遊戲的規則如下:


  1. 先在地上畫N個圓圈,編號1到N,並規定1號圓圈是起點、N號是終點

  2. 在這N個圓圈之間任意互相畫”單向”箭頭,箭頭起點和終點各有一圓圈且兩圓圈不為同一圓,假設有一箭頭從圓a連到圓b,則遊戲中可以從a跳到b。

  3. 檢查1, 2步驟所畫出的圖,確保任何編號1 ~ N-1的圓都有路徑可以走到終點,同時圖中也不可以有迴圈產生(也就是對於任何一個圓,絕對不會有路徑可以從自己走到自己),對任兩圓a, b最多只有一個箭頭從a指向b。

  4. 兩個人進行遊戲,開始時先由一人站在起點(1號圓),另一個人站在圖外。

  5. 遊戲中假設甲站在一個圓 C 中而乙在圖外,則乙要從 C 所指出去的箭頭中選一個箭頭,站到這個箭頭所指的圓上,然後甲則離開C走到圖外。

  6. 兩人重複步驟5的動作,直到其中一人到達終點,到達終點的人為贏家。

例如下圖:

N = 5,假設由Mimi開始,且遊戲過程為
Mimi 在 1, Moumou 到 2, Mimi 到 3, Moumou 到 5 遊戲結束,由Moumou獲勝。

Input Format

輸入檔含有多筆測資,每筆資料第一行有兩個數字 N、E(1 ≦ N ≦ 10000,E ≦ 10N)。接下來 E 行每行有兩個數字 a、b(1 ≦ a, b ≦ N),表示有箭頭從 a 指向 b。你可以假設輸入檔所代表的圖都是有效的。最後一行則是遊戲開始時站在起點上的人名。N 和 E 都是零“0 0”表示檔案結束。

Output Format

假設遊戲為Mimi和Moumou兩人進行,且兩人皆十分聰明,如果有必勝的走法那就一定會贏。

對每筆測資輸出遊戲結束後贏家的名字(Mimi或Moumou),佔一行。

Sample Input 1

5 6
1 2
1 3
2 3
2 4
3 5
4 5
Mimi
0 0

Sample Output 1

Moumou

Hints

Problem Source

原TIOJ1092 / NPSC2006初賽(prob A)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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