Merging Battleships

General Yang Weili is renowned for his brilliant tactics and formations. In a critical battle, he divides the Bamirien Starfield into \(30000\) columns numbered \(1,2,\ldots,30000\). He places his battleships in a single line such that battleship \(i\) occupies column \(i\). This is the initial formation.

When the enemy approaches, Yang issues two types of commands:

• M i j: Merge the entire fleet (i.e. the current column) containing battleship \(i\) and attach it to the tail of the fleet containing battleship \(j\). Note that each fleet is a consecutive sequence of battleships.
• C i j: Query whether battleship \(i\) and battleship \(j\) are in the same column. If they are, report the number of battleships between them. (If they are not in the same column, output -1.)

When battleships are merged, the relative order is preserved. For a query C i j where \(i\) and \(j\) are in the same fleet, let \(d(i)\) and \(d(j)\) be the distances from the head of their fleet. Then the answer is \( |d(i) - d(j)| - 1\). Note that if \(i = j\), there are no battleships between them and the answer is 0.

Your task is to process a sequence of commands in the order they are given. Use an appropriate data structure (such as the union-find with additional distance tracking) to efficiently answer the queries.

inputFormat

The first line contains an integer \(T\) representing the number of commands. Each of the next \(T\) lines contains a command in one of the following two formats:

• M i j — Merge the fleet containing battleship \(i\) and append it to the tail of the fleet containing battleship \(j\).
• C i j — Query if battleship \(i\) and battleship \(j\) are in the same fleet. If they are, output the number of battleships between them; otherwise, output -1.

It is guaranteed that \(1 \leq i, j \leq 30000\) and that the commands are given in a valid order.

outputFormat

For each query command C i j, output one line containing the answer. If \(i\) and \(j\) are in the same fleet, output \(|d(i)-d(j)| - 1\) (the number of battleships between them). Otherwise, output -1.

sample

4
M 2 1
C 1 2
C 2 1
C 1 3

0
0
-1