Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4016
Mergeable Stack

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given $n$ initially empty stacks, there are three types of operations:

• 1 s v: Push the value $v$ onto the top of the $s$-th stack.

• 2 s: Pop the topmost value out of the $s$-th stack, and print that value. If the $s$-th stack is empty, pop nothing and print "EMPTY" (without quotes) instead.

• 3 s t: Move every element in the $t$-th stack onto the top of the $s$-th stack in order.

Precisely speaking, denote the original size of the $s$-th stack by $S(s)$, and the original size of the $t$-th stack by $S(t)$. Denote the original elements in the $s$-th stack from bottom to top by $E(s,1), E(s,2), \dots, E(s,S(s))$, and the original elements in the $t$-th stack from bottom to top by $E(t,1), E(t,2), \dots, E(t,S(t))$.

After this operation, the $t$-th stack is emptied, and the elements in the $s$-th stack from bottom to top becomes $E(s,1), E(s,2), \dots, E(s,S(s)), E(t,1), E(t,2), \dots, E(t,S(t))$. Of course, if $S(t) = 0$, this operation actually does nothing.

There are $q$ operations in total. Please finish these operations in the input order and print the answer for every operation of the second type.

#### Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 3 \times 10^5$), indicating the number of stacks and the number of operations.

The first integer of the following $q$ lines will be $op$ ($1 \le op \le 3$), indicating the type of operation.

• If $op = 1$, two integers $s$ and $v$ ($1 \le s \le n$, $1 \le v \le 10^9$) follow, indicating an operation of the first type.
• If $op = 2$, one integer $s$ ($1 \le s \le n$) follows, indicating an operation of the second type.
• If $op = 3$, two integers $s$ and $t$ ($1 \le s, t \le n$, $s \ne t$) follow, indicating an operation of the third type.

It's guaranteed that neither the sum of $n$ nor the sum of $q$ over all test cases will exceed $10^6$.

#### Output

For each operation of the second type output one line, indicating the answer.

#### Sample Input

2
2 15
1 1 10
1 1 11
1 2 12
1 2 13
3 1 2
1 2 14
2 1
2 1
2 1
2 1
2 1
3 2 1
2 2
2 2
2 2
3 7
3 1 2
3 1 3
3 2 1
2 1
2 2
2 3
2 3


#### Sample Output

13
12
11
10
EMPTY
14
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY


Author: WENG, Caizhi
Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status