Krishna and Stacks

All submissions for this problem are available.
Krishna is playing with stacks. In the beginning of the game, he has an empty stack denoted by number '0'. The game consists of a series of steps. In the ith step of the game, he will choose an existing stack denoted by 'p', copy it (he will create a new copy of it leaving the old one as such) and perform one of the following actions:
Action 1: Place a number 'i' on top of the new stack.
Action 2: Remove a number from the top of the new stack.
Action 3: Choose another stack denoted by 'q' and count how many distinct numbers exist that are in the new stack as well as in the stack 'q' (i.e, the numbers must be in the new stack as well as in the stack 'q' and no repitition is allowed)
He denotes the newly created stack as 'i'.
Now what you have to do is, for each action of type 2, output the number removed from the stack and for each operation of type 3, count the required numbers and output
how many of them there are.
Input
There are many test case files. Each testcase file is described as follows.
The first line of each test case consists of 'n', the number of steps in Krishnaâ€™s game.
The steps of the game are denoted with the first n integers in increasing order.
The ith line of the following 'n' lines contains the description of the ith step of the game in one of the following three forms:
1) "a p" for operation of type 1.
2) "b p" for operation of type 2.
3) "c p q" for operation of type 3.
The first character in the line denotes the type of operation and the next one or two integers denotes the accompanying stack labels that will always be integers from the interval [0, i  1]. It is assured that for each operation of type 2, the stack we are removing the element from will not be empty.
Output
For each operation of type 2 or 3 output the required number.
Constraints
1 <= n <= 3 * 10^5
Example
Input 5 a 0 a 1 b 2 c 2 3 b 4 Output 2 1 2
Explanation
In the beginning, we have the stack S0 = {}. In the first step, we copy S0 and create a new stack. We place the number 1 on top of it and we denote it as stack '1', so S1 = {1}. In the second step, we copy S1 and create a new stack. We place the number 2 on top of it and we denote it as stack '2', and now S2 = {1, 2}. In the third step we copy S2, create a new stack and remove the number 2 from it, S3 = {1}. In the fourth step we copy S2 and denote the copy with S4, then count the numbers appearing in the newly created stack S4 and stack S3, the only such number is '1' so the solution is 1. In the fifth step we copy S4 and remove number 2 from it, S5 = {1}.
Author:  lakshmi8 
Tags  lakshmi8 
Date Added:  19022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 