Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Stack Overflow

By faiyaz26 · Limits 1s, 512 MB

Stack is a basic data structure. Where 3 operations can be done:

  • Push: You can push object to the stack
  • Pop: You can pop the object to the stack
  • Top: You can check the value of the top object.

For further details you can get idea here (if you really don’t know): https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

Now we have a problem here, there are NN stacks in front of you. they are numbered from 1 to NN. Each of them are initially empty. Now you will have QQ operations. Each operation can be one the below 4 types:

  • push i x, Push a value of xx to stack numbered ii
  • pop i, Pop value from the stack numbered ii, if stack is empty discard the operation
  • put i j, Put the jj-th stack on top of the ii-th stack. So there will be no element left on the jj-th stack.
  • top i, Print the value of the top element of ii-th stack. If stack is empty print “Empty!”

Input

Input starts with an integer TT (1T51 ≤ T ≤ 5), denoting the number of test cases.

The next line contains two integers NN (1N1041 ≤ N ≤ 10^4), QQ (1Q5×1041 ≤ Q ≤ 5 \times 10^4). The next QQ lines will contain an operation like above mentioned.

Other constraints:

  • 1i,jN1 ≤ i, j ≤ N
  • 1x1051 ≤ x ≤ 10^5

Output

For each test case, print the case number in a single line. Then for each 4th type operation you should print the value or “Empty!” if the stack is empty.

Sample

InputOutput
1
3 18
push 1 1
push 2 2
push 3 3
push 3 4
top 1
top 2
top 3
put 1 3
pop 2
top 1
top 2
top 3
pop 1
top 1
pop 1
top 1
pop 1
top 1
Case 1:
1
2
4
4
Empty!
Empty!
3
1
Empty!

Discussion

Statistics


67% Solution Ratio

exsurrealEarliest, Aug '15

defaltFastest, 0.0s

exsurrealLightest, 909 kB

habijabiShortest, 492B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.