TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

94.7% (54/57)

Submission's AC Ratio

82.1% (78/95)

Tags

Description

  黑色的騎士團無預警的在校園內發生暴動,在兵荒馬亂之際,你找不到滷肉的身影,但沒辦法,只好自己去避難了。

  衝到宿舍門口時,發現出口居然被堵住了,慌張之下,你逃入原本被禁止通行的地下室。

  在地下室裡,你的面前是個龐大的迷宮,入口前的告示牌上只寫著:此迷宮不會有環狀的路徑

  看到這裡,你突然想到上演算法課時老師所教的『先深法』,於是你決定要用『先深法』『先深』地走遍迷宮找到出口。

  為了避免迷路,所以你決定在『先深』的過程中在每個分岔點以及盡頭做『先深』序號。

Input Format

本題只有一筆測試資料:

第一行有一個數字n,代表說這個迷宮(入口+分岔口+盡頭)的個數(1<=n<=50000)

第二行到第n+1行,各自代表一個地點(第二行是一號、三行是二號...以此類推)
(可能是入口、分岔口或盡頭,但入口一定一號)

每行先有一個k,代表這個地點往下分支有多少個

後面跟著k個數字,代表這個地點往下分支的地點的編號(題目上給的),這k個數字是遞增的

PS.為了方便,總是從邊號較小的分支開始『先深』

Output Format

輸出n行

第i行代表編號i的地點的『先深』序號

Sample Input 1

5
2 2 3
2 4 5
0
0
0

Sample Output 1

1
2
5
3
4

Hints

  走出了迷宮,你發現身處於一個長滿雜草的草地,遠方似乎有個人影,你趕緊趴下身來。

  那人頭上戴了個頭盔,凝神一看....居然是黑色騎士團的領導者零蛋!!

  你呆住了,但更讓你吃驚的是,當零蛋把頭盔拿下來時,他居然是你的摯友滷肉!!

※2008/07/17 測資範圍修正 by hallogameboy。
※2012/04/14 輸入敘述增修 by tmt514。

Problem Source

原TIOJ1369 / 快樂暑假營第二次練習比賽。Problem Setter:hallogameboy

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

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