Problem:
Splice For $n$ lists $L_i$ $(i = 0, 1, ..., n-1)$, perform a sequence of the following operations.  insert($t$, $x$): Insert an integer $x$ at the end of $L_t$.  dump($t$): Print all elements in $L_t$.  splice($s$, $t$):　Transfer elements of $L_s$ to the end of $L_t$. $L_s$ becomes empty.  In the initial state, $L_i$ $(i = 0, 1, ..., n-1)$ are empty. Input The input is given in the following format. $n \; q$
$query_1$
$query_2$
:
$query_q$ Each query $query_i$ is given by 0 $t$ $x$ or 1 $t$ or 2 $s$ $t$ where the first digits 0 , 1 and 2 represent insert, dump and splice operations respectively. Output For each dump operation, print elements of the corresponding list in a line. Separete adjacency elements by a space character (do not print the space after the last element). Note that, if the list is empty, an empty line should be printed. Constraints  $1 \leq n \leq 1,000$  $1 \leq q \leq 500,000$  For a splice operation, $s \ne t$  For a splice operation, $L_s$  is not empty  The total number of elements printed by dump operations do not exceed 1,000,000  $-1,000,000,000 \leq x \leq 1,000,000,000$  Sample Input 1 3 10
0 0 1
0 0 2
0 0 3
0 1 4
0 1 5
2 1 0
0 2 6
1 0
1 1
1 2 Sample Output 1 1 2 3 4 5

6

Solution (Python):
class Node:
  def __init__(self,key):
    self.key = key
    self.next = None

class List:
  def __init__(self):
    self.head = Node(0)
    self.tail = self.head

  def insert(self,key):
    self.tail.next = Node(key)
    self.tail = self.tail.next

  def dump(self):
    p = self.head.next
    while p != None:
      print(p.key, end='')
      if p.next != None:
        print(' ',end='')
      p = p.next
    print()

  def splice(self,other):
    other.tail.next = self.head.next
    other.tail = self.tail
    self.head.next = None
    self.tail = self.head

''' main function '''
n,q = map(int,input().split())

SList = [List() for i in range(n)]

for i in range(q):
  com,index,*n = map(int,input().split())
  if com == 0:
    SList[index].insert(n[0])
  elif com == 1:
    SList[index].dump()
  elif com == 2:
    SList[index].splice(SList[n[0]])

Solution (Python):
class Node:
    def __init__(self, val=None, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class DoublyLinkedList():
    def __init__(self):
        self.start = Node(val='START', prev=None, next=None)
        self.end = Node(val='END', prev=self.start, next=None)
        self.start.next = self.end

    def insert(self, x):
        new_node = Node(val=x, prev=self.end.prev, next=self.end)
        self.end.prev.next = new_node
        self.end.prev = new_node

    def dump(self):
        node_list = []
        crnode = self.start.next
        while crnode != self.end:
            node_list.append(crnode.val)
            crnode = crnode.next
        print(' '.join(list(map(str, node_list))))

    def extend(self, dll):
        self.end.prev.next = dll.start.next
        dll.start.next.prev = self.end.prev
        self.end = dll.end

n, q = list(map(int, input().split(' ')))
splice = [DoublyLinkedList() for i in range(n)]

for i in range(q):
    op, *val = list(map(int, input().split(' ')))
    if op == 0:
        splice[val[0]].insert(val[1])
    elif op == 1:
        splice[val[0]].dump()
    else:
        splice[val[1]].extend(splice[val[0]])
        splice[val[0]] = DoublyLinkedList()

Solution (Python):

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class List:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, v):
        node = Node(v)
        if self.tail is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dump(self):
        node = self.head
        while node is not None:
            yield node.value
            node = node.next

    def splice(self, li):
        if self.head is None:
            self.head = li.head
            self.tail = li.tail
        else:
            self.tail.next = li.head
            self.tail = li.tail
        li.clear()

    def clear(self):
        self.head = None
        self.tail = None


def run():
    n, q = [int(x) for x in input().split()]
    ls = [List() for _ in range(n)]

    for _ in range(q):
        com = [int(x) for x in input().split()]
        c = com[0]
        if c == 0:
            t, v = com[1:]
            ls[t].insert(v)
        elif c == 1:
            t = com[1]
            values = []
            for v in ls[t].dump():
                values.append(str(v))
            print(" ".join(values))
        elif c == 2:
            s, t = com[1:]
            ls[t].splice(ls[s])
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Solution (Python):
from collections import deque
n,q=map(int, input().split())

L={i:deque() for i in range(n)}

for _ in range(q):
    *qi,=map(int, input().split( ))
    if qi[0]==0:
        t,x=qi[1],qi[2]
        L[t].append(x)
    elif qi[0]==1:
        print(*L[qi[1]])
    else:
        s,t=qi[1],qi[2]
        if len(L[s])<len(L[t]):
            L[t].extend(L[s])
            L[s]=deque()
        else:
            while L[t]:
                L[s].appendleft(L[t].pop())
            L[t]=L[s]
            L[s]=deque()

Solution (Python):
import sys
from collections import defaultdict, deque

sys.stdin.readline().split()
A = defaultdict(deque)
ans = []

for query in sys.stdin:
    if query[0] == '0':
        t, x = query[2:].split()
        A[t].append(x)
    elif query[0] == '1':
        ans.append(' '.join(A[query[2:-1]]) + '\n')
    else:
        s, t = query[2:].split()
        if A[t]:
            if len(A[s]) == 1:
                A[t].append(A[s][0])
            elif len(A[t]) == 1:
                A[s].appendleft(A[t][0])
                A[t] = A[s]
            else:
                A[t].extend(A[s])
        else:
            A[t] = A[s]
        A[s] = deque()

sys.stdout.writelines(ans)

Solution (Python):
def resolve():
    import sys
    from collections import deque
    def input(): return sys.stdin.readline().rstrip()
    n, Q = [int(i) for i in input().split()]
    A = [deque() for _ in range(n)]
    for _ in range(Q):
        q = [int(i) for i in input().split()]
        if q[0] == 0:
            A[q[1]].append(q[2])
        elif q[0] == 1:
            print(*A[q[1]])
        else:
            if len(A[q[2]]) == 0:
                A[q[2]] = A[q[1]]
            else:
                if len(A[q[2]]) == 1:
                    A[q[1]].appendleft(A[q[2]][0])
                    A[q[2]] = A[q[1]]
                else:
                    A[q[2]].extend(A[q[1]])
            A[q[1]] = deque()


resolve()

Solution (Python):
from collections import deque

def insert(t, x):
    Llist[t].append(x)

def dump(t):
    print(*Llist[t])


def splice(s, t):
    if Llist[t]:
        if len(Llist[t]) ==1:
            Llist[s].appendleft(Llist[t][0])
            Llist[t] = Llist[s]
        elif len(Llist[s]) == 1:
            Llist[t].append(Llist[s][0])
        else:   
            Llist[t].extend(Llist[s])
    else:
        Llist[t] = Llist[s]

    Llist[s] = deque() 

n, q = map(int, input().split())

Llist = []

for i in range(n):
    Llist.append(deque())

for i in range(q):
    queryi = list(map(int, input().split()))

    if queryi[0] == 0:
        insert(queryi[1], queryi[2])
    
    elif queryi[0] == 1:
        dump(queryi[1])
    
    else:
        splice(queryi[1], queryi[2])

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().strip()
n,q = map(int,input().split())

L = deque(deque() for i in range(n))

for i in range(q):
    query = input().split()

    if query[0] == "0":
        L[int(query[1])].append(query[2])
    elif query[0] == "1":
        print(" ".join(L[int(query[1])]))
    else:
        s = int(query[1])
        t = int(query[2])
        if len(L[s]):
            if len(L[t]) == 0:
                L[t] = L[s]
            elif len(L[t]) == 1:
                L[s].appendleft(L[t][0])
                L[t] = L[s]
            else:
                L[t].extend(L[s])
        elif len(L[s]) == 1:
            L[t].append(L[t][0])
        L[s] = deque()

Solution (Python):
from collections import deque
n, q = map(int, input().split())
lists = [deque() for i in range(n)]
while q:
    q -= 1
    s = [*map(int, input().split())]
    if s[0] == 0:
        lists[s[1]].append(s[2])
    elif s[0] == 1:
        print(*lists[s[1]])
    else:
        l1, l2 = lists[s[1]], lists[s[2]]
        if len(l1) < len(l2):
            l2.extend(l1)
            l1.clear()
        else:
            while len(l2):
                l1.appendleft(l2[-1])
                l2.pop()
            lists[s[1]], lists[s[2]] = lists[s[2]], lists[s[1]]

Solution (Python):
import sys
from collections import deque,defaultdict

A = defaultdict(deque)
sys.stdin.readline().split()
ans =[]
for query in sys.stdin:
    if query[0] == "0":
        t,x = query[2:].split()
        A[t].append(x)
    elif query[0] == "1":
        ans.append(" ".join(A[query[2:-1]]) + "\n")
    else:
        s,t = query[2:].split()
        if A[t]:
            if len(A[s]) == 1:
                A[t].append(A[s][0])
            elif len(A[t]) == 1:
                A[s].appendleft(A[t][0])
                A[t] = A[s]
            else:
                A[t].extend(A[s])
        else:
            A[t] = A[s]
        A[s] = deque()
sys.stdout.writelines(ans)

Solution (Python):
import sys
input = sys.stdin.readline

from collections import deque

N,Q = map(int,input().split())

L = [deque([]) for _ in range(N)]

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        L[q[1]].append(q[2])
    elif q[0] == 1:
        if L[q[1]]:
            print(' '.join(map(str,L[q[1]])))
        else:
            print()
    else:
        if L[q[1]]:
            if L[q[2]]:
                if len(L[q[1]]) == 1:
                    L[q[2]].append(L[q[1]][0])
                elif len(L[q[2]]) == 1:
                    L[q[1]].appendleft(L[q[2]][0])
                    L[q[2]] = L[q[1]]
                else:
                    L[q[2]].extend(L[q[1]])
            else:
                L[q[2]] = L[q[1]]
        L[q[1]] = deque([])

Solution (Python):
from collections import deque

n, q = list(map(int, input().split()))
L = [deque() for _ in range(n)]

for i in range(q):
    query = input()

    
    if query[0] == "0":
        _, t, x = list(map(int, query.split()))
        L[t].append(x)

    
    elif query[0] == "1":
        _, t = list(map(int, query.split()))
        print(*L[t])
    
    
    else:
        _, s, t = list(map(int, query.split()))
        if L[t]:
            if len(L[s]) == 1:
                L[t].append(L[s][0])
            elif len(L[t]) == 1:
                L[s].appendleft(L[t][0])
                L[t] = L[s]
            else:
                L[t].extend(L[s])
        else:
            L[t] = L[s]

        L[s] = deque()

Solution (Python):
import heapq
import collections
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
L = [collections.deque() for i in range(n)]

queries = list()
for i in range(q):
    queries.append(list(map(int, input().split())))

for query in queries:
    if query[0] == 0:
        L[query[1]].append(query[2])
    elif query[0] == 1:
        print(*L[query[1]])
    elif query[0] == 2:
        if L[query[2]]:
            if len(L[query[1]]) == 1:
                L[query[2]].append(L[query[1]][0])
            elif len(L[query[2]]) == 1:
                L[query[1]].appendleft(L[query[2]][0])
                L[query[2]] = L[query[1]]
            else:
                L[query[2]].extend(L[query[1]])
        else:
            L[query[2]] = L[query[1]]
        L[query[1]] = collections.deque()

Solution (Python):
from collections import deque

def main():
    n, q = map(int, input().split())
    li = [ deque() for i in range(n)]

    for _ in range(q):
        command, *para = map(int, input().split())

        if   command == 0:
            li[para[0]].append(para[1])
            
        elif command == 1:
            print(*li[para[0]])

        elif command == 2:

            if  not li[para[0]]:
                continue

            if not li[para[1]]:
                li[para[1]] = li[para[0]]
                
            elif   len(li[para[0]]) == 1:
                li[para[1]].append(li[para[0]][0])
            elif len(li[para[1]]) == 1:
                li[para[0]].appendleft(li[para[1]][0])
                li[para[1]] = li[para[0]]
            else:
                li[para[1]].extend(li[para[0]])

            li[para[0]] = deque()

main()

Solution (Python):
import sys
input = sys.stdin.readline

from collections import deque

N,Q = map(int,input().split())

L = [deque([]) for _ in range(N)]

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        L[q[1]].append(q[2])
    elif q[0] == 1:
        if L[q[1]]:
            print(' '.join(map(str,L[q[1]])))
        else:
            print()
    else:
        if L[q[1]]:
            if L[q[2]]:
                if len(L[q[1]]) == 1:
                    L[q[2]].append(L[q[1]][0])
                elif len(L[q[2]]) == 1:
                    L[q[1]].appendleft(L[q[2]][0])
                    L[q[2]] = L[q[1]]
                else:
                    L[q[2]].extend(L[q[1]])
            else:
                L[q[2]] = L[q[1]]
        L[q[1]] = deque([])

Solution (Python):
import collections


class Splice():
    def __init__(self, num_lists):
        self.lists = [collections.deque() for i in range(0, num_lists, 1)]

    def insert(self, t, x):
        self.lists[t].append(x)
        return self

    def dump(self, t):
        print(' '.join(map(str, self.lists[t])))

    def splice(self, s, t):
        if self.lists[t]:
            if len(self.lists[s]) == 1:
                self.lists[t].append(self.lists[s][0])
            elif len(self.lists[t]) == 1:
                self.lists[s].appendleft(self.lists[t][0])
                self.lists[t] = self.lists[s]
            else:
                self.lists[t].extend(self.lists[s])
        else:
            self.lists[t] = self.lists[s]
        self.lists[s] = collections.deque()
        return self


num_lists, num_op = map(int, input().split(' '))
lists = Splice(num_lists)

for op in range(0, num_op):
    op = tuple(map(int, input().split(' ')))
    if op[0] == 0:
        lists.insert(op[1], op[2])
    elif op[0] == 1:
        lists.dump(op[1])
    elif op[0] == 2:
        lists.splice(op[1], op[2])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)

n,q = map(int, input().split())
l = [deque() for _ in range(n)]

for _ in range(q):
	query = input().split()
	if query[0] == "0": 
		idx = int(query[1])
		l[idx].append(query[2])
	elif query[0] == "1": 
		idx = int(query[1])
		print(" ".join(l[idx]))
	elif query[0] == "2": 
		idx1 = int(query[1])
		idx2 = int(query[2])
		if len(l[idx1]) > 1:
			if len(l[idx2]) == 0:
				l[idx2] = l[idx1]
			elif len(l[idx2]) == 1:
				l[idx1].appendleft(l[idx2][0])
				l[idx2] = l[idx1]
			else:
				l[idx2].extend(l[idx1])
		elif len(l[idx1]) == 1:
			l[idx2].append(l[idx1][0])
		l[idx1] = deque()

Solution (Python):

from collections import deque
n, q = [int(x) for x in input().split()]
L = [ deque() for _ in range(n) ]
for _ in range(q):
    c, t, x = [int(x) for x in (input()+" 0").split()][:3]
    if c == 0:
        L[t].append(x)
    elif c == 1:
        print( " ".join(map(str,L[t])))
    else:
        s,t = t, x
        if L[s]:
            if L[t]:
                if len(L[s]) == 1:
                    L[t].append(L[s][0])
                elif len(L[t]) == 1:
                    L[s].appendleft(L[t][0])
                    L[t] = L[s]
                else:
                    L[t].extend(L[s])
            else:
                L[t] = L[s]
            L[s] = deque()

Solution (Python):
from collections import deque
import sys

n, q = map(int, input().split())


Q = [deque() for _ in range(n)]
ans = []
for query in (line.split() for line in sys.stdin):
    s = int(query[1])
    if query[0] == '0':
        t = int(query[2])
        Q[s].append(t)
    elif query[0] == '1':
        
        print(*Q[s])
    elif query[0] == '2':
        t = int(query[2])
        if Q[t]:
            if len(Q[s]) == 1:
                Q[t].append(Q[s][0])
            elif len(Q[t]) == 1:
                Q[s].appendleft(Q[t][0])
                Q[t] = Q[s]
            else:
                Q[t].extend(Q[s])
                
        else:
            Q[t] = Q[s]
        Q[s] = deque()

Solution (Python):
from collections import deque


if __name__ == "__main__":
    que_num, query_num = map(lambda x: int(x), input().split())
    ques = [deque() for _ in range(que_num)]  

    for _ in range(query_num):
        op, *value = map(lambda x: int(x), input().split())
        if (0 == op):
            ques[value[0]].append(value[1])
        elif (1 == op):
            if ques[value[0]]:
                print(" ".join([str(elem) for elem in ques[value[0]]]))
            else:
                print("")
        elif (2 == op):
            if ques[value[1]]:
                if (len(ques[value[0]]) == 1):
                    ques[value[1]].append(ques[value[0]][0])
                elif (len(ques[value[1]]) == 1):
                    ques[value[0]].appendleft(ques[value[1]][0])
                    ques[value[1]] = ques[value[0]]
                else:
                    ques[value[1]] += ques[value[0]]
            else:
                ques[value[1]] = ques[value[0]]
            ques[value[0]] = deque()
        else:
            pass

Solution (Python):
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    n, q = map(int, f_i.readline().split())
    
    L = [deque() for i in range(n)]
    ans = []
    for op in (line.split() for line in f_i):
        op_type = op[0]
        if op_type == '0':
            L[int(op[1])].append(op[2])
        elif op_type == '1':
            ans.append(' '.join(L[int(op[1])]))
        else:
            s = int(op[1])
            ls = L[s]
            t = int(op[2])
            lt = L[t]
            if lt:
                if len(ls) == 1:
                    lt.append(ls[0])
                elif len(lt) == 1:
                    ls.appendleft(lt[0])
                    L[t] = ls
                elif ls:
                    lt.extend(ls)
            else:
                L[t] = ls
            L[s] = deque()
    print('\n'.join(ans))

solve()

Solution (Python):
from sys import stdin,stdout
from collections import defaultdict,deque

n, q = map(int,stdin.readline().split())
queries = stdin.readlines()
A = defaultdict(deque)
ans = []

for query in queries:
    
    
    query = query.split()
    if query[0] == '0':
        A[int(query[1])].append(query[2])
    elif query[0] == '1':
        ans.append(' '.join(A[int(query[1])]) + '\n')
    else:
        s = int(query[1])
        t = int(query[2])
        if (A[t]):
            if len(A[s]) == 1:
                A[t].append(A[s][0])
            elif len(A[t]) == 1:
                A[s].appendleft(A[t][0])
                A[t] = A[s]
            else:
                A[t].extend(A[s])
        else:
            A[t] = A[s]
        A[s] = deque()

stdout.writelines(ans)

Solution (Python):

"""
Basic Data Structures - Splice
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_2_D&lang=jp

"""

class Node:
    def __init__(self, value=0):
        self.key = value
        self.prev, self.next = None, None

class Lst:
    def __init__(self):
        self.nil = Node('END')
        self.nil.next = self.nil
        self.nil.prev = self.nil
        self.cur = self.nil

    def insert(self, value):
        x = Node(value)
        x.prev = self.cur
        x.prev.next = x
        x.next = self.nil
        self.cur = x

    def dump(self):
        res = []
        cur = self.nil
        while cur.next.key != 'END':
            cur = cur.next
            res.append(cur.key)
        print(*res)

class Sp:
    def __init__(self, n):
        self.lst = [Lst() for _ in range(n)]

    def insert(self, t, x):
        self.lst[t].insert(x)

    def dump(self, t):
        self.lst[t].dump()

    def splice(self, s, t):
        self.lst[t].cur.next = self.lst[s].nil.next
        self.lst[s].nil.next.prev = self.lst[t].cur
        self.lst[t].cur = self.lst[s].cur
        self.lst[s] = Lst()


n, q = map(int, input().split())
lst = Sp(n)
for _ in range(int(q)):
    op, t, x = (input() + ' 1').split()[:3]
    if op == '0':
        lst.insert(int(t), int(x))
    elif op == '1':
        lst.dump(int(t))
    else:
        lst.splice(int(t), int(x))

Solution (Python):
from collections import deque
n, queries = map(int, input().split())
L = [deque() for _ in range(n)]

for _ in range(queries):
    q, *list_num = input().split()
    if q == '0':
        t = int(list_num[0])
        x = int(list_num[1])
        L[t].append(x)
    elif q == '1':
        t = int(list_num[0])
        print(*L[t])
    elif q == '2':
        s = int(list_num[0])
        t = int(list_num[1])
        if not L[s]:
            continue
        if L[t]:
            if len(L[s]) == 1:
                L[t].append(L[s][0])
            elif len(L[t]) == 1:
                L[s].appendleft(L[t][0])
                L[t] = L[s]
            else:
                L[t].extend(L[s])
        else:
            L[t] = L[s]
        L[s] = deque()

Solution (Python):
from collections import deque



n, q = map(int, input().split())

L = [deque() for _ in range(n)]


for _ in range(q):

    command, *list_num = input().split()

    if   command == "0":
        
        t = int(list_num[0])
        x = int(list_num[1])

        L[t].append(x)
    elif command == "1":
        
        t = int(list_num[0])

        print(*L[t])
    elif command == "2":
        
        s = int(list_num[0])
        t = int(list_num[1])

        if not L[s]:
            continue

        if L[t]:
            if   len(L[s]) == 1:
                L[t].append(L[s][0])
            elif len(L[t]) == 1:
                L[s].appendleft(L[t][0])
                L[t] = L[s]
            else:
                L[t].extend(L[s])
        else:
            L[t] = L[s]

        L[s] = deque()
    else:
        raise

Solution (Python):
import sys

class Node:
    def __init__(self, next_node, prev_node, val):
        self.next = next_node
        self.prev = prev_node
        self.val = val

    def __repr__(self):
        return f'{self.val}'


class DoubleLinkedList:
    def __init__(self):
        self.head = Node(None, None, None)
        self.tail = self.head

    def append(self, val):
        node = Node(None, self.tail, val)
        self.tail.next = node
        self.tail = node

    def dump(self):
        cur = self.head.next
        out = ''
        while cur is not None:
            out += f'{cur.val} '
            cur = cur.next
        print(out[:-1])

    def splice(self, other):
        self.tail.next = other.head.next
        self.tail = other.tail

    def clear(self):
        self.__init__()


n, q = map(int, input().split())

lists = {str(i): DoubleLinkedList() for i in range(n)}

lines = sys.stdin.readlines()
for i in range(q):
    query, *arg = lines[i].split()
    
    if query == '0':    
        lists[arg[0]].append(arg[1])

    elif query == '1':  
        lists[arg[0]].dump()

    elif query == '2':  
        lists[arg[1]].splice(lists[arg[0]])
        lists[arg[0]].clear()

    else:
        raise AssertionError

Solution (Python):
import sys
from collections import defaultdict, deque
sys.stdin.readline().split()
A = defaultdict(deque)
ans = []
for query in sys.stdin:
    if query[0] == '0':
        t, x = query[2:].split()
        A[t].append(x)
    elif query[0] == '1':
        ans.append(' '.join(A[query[2:-1]]) + '\n')
    else:
        s, t = query[2:].split()
        if A[t]:
            if len(A[s]) == 1:
                A[t].append(A[s][0])
            elif len(A[t]) == 1:
                A[s].appendleft(A[t][0])
                A[t] = A[s]
            else:
                A[t].extend(A[s])
        else:
            A[t] = A[s]
        A[s] = deque()
sys.stdout.writelines(ans)

Solution (Python):
from collections import deque
readline = open(0).readline
writelines = open(1, 'w').writelines
N, Q = map(int, readline().split())
ans = []
A = [deque() for i in range(N)]
def push(t, x):
    A[t].append(str(x))
def dump(t):
    ans.append(" ".join(A[t]))
    ans.append("\n")
def splice(s, t):
    if A[s]:
        if A[t]:
            if len(A[s]) == 1:
                A[t].append(A[s][0])
            elif len(A[t]) == 1:
                A[s].appendleft(A[t][0])
                A[t] = A[s]
            else:
                A[t].extend(A[s])
        else:
            A[t] = A[s]
        A[s] = deque()

C = [push, dump, splice].__getitem__
for i in range(Q):
    t, *a=map(int, readline().split())
    C(t)(*a)
writelines(ans)