TopCoder

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

75.0% (21/28)

Tags

Description

大家有沒有遇過一群人無法馬上做下決定的事情呢?
例如今天晚餐要吃什麼、跨年要去哪裡狂歡、晚餐錢要誰出之類的問題…

猜拳已經落伍啦!現在最流行的(?)是鬼腳圖(好啦,其實大家一定玩過…)

曾經是高中同學的三毅阿正兩瑋韋衖小雷五個人,在美好的2007寒假,決定辦一個同學會。
但是需要進行的準備事項有五:場地、活動、聯絡、開會、茶點。
每個人做這五項工作都沒問題,但還是需要分配一下,於是他們畫了一張這樣的圖:


1 2 3 4 5
| | | | |
+---+ +---+ |
| | | | |
| +---+ | |
| | | +---+
+---+ | | |
| | | | |
+---+ | | |
| | | | |
A B C D E

五個人A,B,C,D,E沿著各自的線走,遇到岔路就一定要轉彎,而且不能往走,最後一定會走到1,2,3,4,5五件工作其中之一。
阿正驚訝的發現五個人走到的五件工作都不會重複!

今年是2008年,這次的同學會由於擴大舉辦,總共有N個人要負責N件事情
阿正如法炮製畫了一個類似的圖,但是由於太過複雜,阿正沒辦法確定到底每個人該做什麼事情,於是他請德育要求時弦麻煩球主商請阿棠請託蛋蛋有請川弘告訴…(族繁不急被宰)…蕃茄拜託你,來寫一個程式來求出每個人該負責的工作。

Input Format

輸入可能包含多筆測試資料,每筆測試資料的第一列有兩個正整數n(1<=n<=100)以及m(0<=m<=100,000)。
接下來有m列每列有4*n-3個字元,形成一個鬼腳圖。(為了方便起見,下面的入口由左而右依序是第1,2,...,n人,這樣就不必寫出這n個人的名字了,上面的終點依序代表編號1,2,...,n的工作,同樣的在輸入中也不會出現)

當n=m=0時代表輸入結束。

輸入的所有鬼腳圖不會有不合理的地方,所有的叉路都不會有猶豫不決的情況。

Output Format

對每一筆測試資料,請輸出一列,包含n個以一個空白間隔的數字,第i個數字代表第i個人分配到的工作編號。
注意不要輸出行尾的空白。

Sample Input 1

5 6
| | | | |
+---+ +---+ |
| | | | |
| +---+ +---+
| | | | |
| | | | |
1 0
2 1
+---+
0 0

Sample Output 1

2 4 1 5 3
1
2 1

Hints

可考慮使用gets()或cin.getline()一次輸入一列字元。

※2008/01/20題目修正:感謝jack。

Problem Source

原TIOJ1188 / TIOJ 2008例行賽01 (prob D)。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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