TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

90.6% (173/191)

Submission's AC Ratio

30.4% (334/1100)

Tags

Description

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

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


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

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

  3. 檢查 1, 2 步驟所畫出的圖,確保任何編號 $1\sim 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 \leq N \leq 10^ 4,E \leq 10N$)。接下來 $E$ 行每行有兩個數字 $a,b$($1 \leq a, b \leq 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