TopCoder

User's AC Ratio

74.2% (23/31)

Submission's AC Ratio

45.5% (51/112)

Tags

Description

每年到了初春,公仔公司都會發行一款限量版的鋼彈模型,因為實在非常稀有,往往都造成大排長龍。這天你陪著你的朋友史阿翟一大早就來到了公仔購買處排隊,原本感覺和發放處的距離很近,大約隔了 $30$ 個人的距離。想不到隨著時間遷移,和發放處的距離不但沒有減少,反而似乎還增多了!

感到困惑的你於是離開了排隊的隊伍,到隊伍的側面仔細觀察,這才發現不知不覺之間,史阿翟和發放處中間已經隔了超過 $2217$ 個人了!原來他們忽略了一件事情:他們是在中國境內的香__排隊的,想當然爾來排隊的大部分都是中國人。然而中國人排隊的方式是很有趣的:有些中國人彼此認識,我們稱他們為「同夥的」。一個中國人來排隊時,如果整個隊列內沒有任何一個與他同夥的人,那麼他就只好乖乖排隊;否則他就會找到他的同夥,然後排在他的最後面(如果有多個同夥,那就排在最後一個同夥的後面)。注意到這在中國人的語言內叫做「給個方便」,絕對不是什麼「插隊」之類的惡劣的行為。

看到這個現象,你想要估計一下史阿翟到底還要排多久才會排得到隊,於是你想先寫一個程式,在假設已知哪些人是同夥的以及隊列變動的情況下,模擬出這個排隊隊列的情形。

Input Format

為了方便起見,我們用編號來表示每一個人,所有人的編號都是介於 $0 \sim 999999$ 之間的整數。

輸入的第一行包含一個正整數 $T(T \leq 20)$,代表測試資料的數量

對於每組測試資料,輸入的第一行有一個正整數 $N(N \leq 1000)$,代表總共有多少團中國人,其中同一團內的中國人都是一夥的。

接著有 $N$ 行,每行都代表一團中國人的資訊。其中第 $i$ 行的第一個數是一個正整數 $K_i(K_i \leq 1000)$,代表第 $i$ 團內有幾個成員。接著有 $K_i$ 個整數,代表有哪幾個編號的成員屬於這夥。因為中國人感情很好,所以不會有一個人同時隸屬於兩夥人的狀況。

接下來有一個數字 $M (M \leq 200000)$,代表敘述的數量

接下來的 $M$ 行,每行代表一個敘述,敘述有兩種:
ENQUEUE x:編號x的人加入排隊的行列
DEQUEUE:隊列最前面的人領到公仔,離開隊伍

DEQUEUE的時候保證至少有一個人還在排隊
ENQUEUE的時候不會有該編號的人已經在排隊了卻還要ENQUEUE的情況
領過公仔的人不會再去排隊

$\Sigma M\leq 200000$

Output Format

對於每組測資,請先輸出一行「Line #k」(不含括號),其中 $k$ 代表這是第幾組測試資料。接著對於每一個DEQUEUE的指令,請輸出這位幸運拿到公仔的人是誰,一個指令一行。

Sample Input 1

2
2
3 1 2 3
4 4 5 6 7
12
ENQUEUE 1
ENQUEUE 4
ENQUEUE 3
ENQUEUE 2
ENQUEUE 8
ENQUEUE 6
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
2
3 10000 20000 30000
4 400000 500000 600000 700000
12
ENQUEUE 10000
ENQUEUE 400000
ENQUEUE 30000
DEQUEUE
DEQUEUE
ENQUEUE 700000
ENQUEUE 600000
ENQUEUE 500000
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE

Sample Output 1

Line #1
1
3
2
4
6
8
Line #2
10000
30000
400000
700000
600000
500000

Hints

Problem Source

UVa
NEOJ Problem 20

Subtasks

No. Testdata Range Constraints Score
1 0~3 100

Testdata and Limits

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