19 . 中國人排隊問題
TopCoder
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
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
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 |