Cube Stacking

Interview

Time limit2sMemory limit1024 MB

Summary

Starting from N single-cube stacks, process moves that place one stack on top of another and queries that count the cubes beneath a given cube.

Level: Medium5 of 10
Topics: Union-find, Array
Solved: No attempts yet

Problem

Farmer John and Betsy play a game with N identical cubes labeled 1 through N (1 ≤ N ≤ 30,000). At the start, there are N stacks, each holding a single cube. Farmer John asks Betsy to perform P operations (1 ≤ P ≤ 100,000). There are two types of operations: moves and counts.

In a move operation, Betsy moves the stack containing cube X on top of the stack containing cube Y.
In a count operation, Betsy counts the cubes under cube X in the stack that contains cube X and reports that value.

Write a program that verifies the results of the game.

Input

The first line contains a single integer P. Each of the next P lines describes one legal operation. A line begins with M for a move operation or C for a count operation. A move line contains two integers, X and Y. A count line contains one integer, X.

The value of N is not given in the input. No move operation moves a stack onto itself.

Output

Print the result of each count operation in the order they appear in the input, one per line.

Examples1

Example 1
Input
```
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
```
Expected output
```
1
0
2
```