14. 排隊問題

0 Judge

Code: 0


排隊問題

題目敘述

sprout
ㄠㄨ

一開始有$n$個人,編號為$1\sim n$,總共有$n$個隊伍,編號也是$1\sim n$。現在讓編號$1$的人排在編號$1$的隊伍、編號$2$的人排在編號$2$的隊伍...編號$n$的人排在編號$n$的隊伍。接著有$m$個指令,必須按先輸入後順序執行,指令有兩種,分別是0 a和,1 a b,兩種指令解說如下:

  • 0 a b
    表示編號$a$的人從原來的位置離開,排到編號$b$的人的後面
  • 1 a b
    表示編號$a$的隊伍的所有人,按原來順序排到編號$b$的隊伍的尾端,注意編號$a$的隊伍和編號$b$的隊伍都有可能沒人排隊

請你在所有操作都完成後,按順序輸出每一隊的人。

輸入說明

第一行有兩個整數$\;n,\;m$,$1 \leq n \leq 10^6,\;1 \leq m \leq 2*10^6$,接著有m行,每行有三個整數$\;t,\;a,\;b$,$t = 0 \; or \; 1,\; 1 \leq a \leq n,\;1 \leq b \leq n,\; a \neq b$。

輸出說明

按造順序輸出每一隊在所有操作都完成後的情況,行尾不能有空白,詳見範例輸入輸出。

範例輸入

6 4
0 4 3
0 6 5
1 2 5
1 6 5

範例輸出

#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

配分方法

  • 10% $n \leq 100$
  • 20% $n \leq 1000$
  • 30% $n \leq 10^4$
  • 40% $n \leq 10^6$

Hints

實作linked list

備註

關於範例測資,一開始的時候長這樣:
#1: 1
#2: 2
#3: 3
#4: 4
#5: 5
#6: 6
第一次操作:
#1: 1
#2: 2
#3: 3 4
#4:
#5: 5
#6: 6
第二次操作:
#1: 1
#2: 2
#3: 3 4
#4:
#5: 5 6
#6:
第三次操作:
#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:
第四次操作:
#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

Judge Setting

run-time limit: 3000 ms
memory limit: 19660800 byte
測資數量: 0