National Olympiad in Informatics, China, 2002

Day 1, Problem 1 - Legend of the Galactic Heroes

In the year 2801 CE, the Earth's inhabitants have migrated to Theoria, the second planet of the Aldebaran Starzone in the Taurus constellation. There and then, the Galactic Federation was officially founded. That same year, the Common Era (CE) calendar was replaced by the Universal Calender (UC) to commemorate this establishment. Subsequently, further expansion into the depths of the galaxy commenced.

In the year 799 UC, battle erupted between the two largest military forces of the galaxy in the Vermilion Starzone. The Galactic Empire ordered commander Reinhard von Lohengramm to take a fleet of roughly one hundred thousand warships to demolish the thirty thousand opposing ships under the command of admiral Yang Wen-li.

Yang Wen-li specializes in directing soldiers and battle formations. In the past, he has won countless battles using brilliant tactics, especially when grossly outnumbered. Inevitably, his pride grows with every battle. During this ultimate battle, he has divided the battlefield of Vermilion into 30000 columns, each column labeled with a number from 1 to 30000. He has also labeled his warships with a number from 1 to 30000, allowing ship i to occupy column i (i = 1, 2, …, 30000), creating a "one-rowed snake formation" to lure the enemy deep within the trap. This is only the initial formation. When the invading enemies arrive, Yang Wen-li will repeatedly issue commands to merge his ships to focus attacks on particular rows. A merge command is of the format M i j, indicating that the entire fleet in the column containing ship i should move, as a whole, to the back of the entire fleet containing ship j. Obviously, the entire fleet can consist of one or more warships from the same column. The merge command will result in an increase in the size of the destination column.

However, the cunning Reinhard had long been a step ahead. At any time during the battle, he will be able to use a vast intelligence network to listen in on Yang Wen-li's commands for directing his fleet.

While Yang Wen-li is issuing a command to transfer his fleets, some queries will be issued in the format C i j. This command asks the computer: do Yan Wen-li's ship i and ship j currently belong in the same column? If so, how many ships are positioned between them?

As an experienced senior programmer, you have been requested to write a program that analyzes Yang Wen-li's orders, as well as answers Reinhard's queries.

The final battle has begun, thus starting a new chapter in the galaxy's history.

Input Format

The first line of input contains a single integer T (1 ≤ T ≤ 500,000), representing the total number of commands. The following T lines each contain a command of the following two formats:

1. M i j : where i and j are two integers (1 ≤ i, j ≤ 30,000), representing the numbers of the ships involved. These are commands issued by Yang Wen-li and secretly obtained by commander Reinhard. It is guaranteed that ship i and ship j are not already in the same column.
2. C i j : where i and j are two integers (1 ≤ i, j ≤ 30,000), representing the numbers of the ships involved. These are queries made by Reinhard about the status of Yang Wen-li's fleet.

Output Format

You are to analyze and process the commands in the input. For each of Yang Wen-li's commands that indicate a merge of fleets, your program should take note of the change but not output any information. For each of Reinhard's queries, your program must output one line containing a single integer. If ships i and j are in the same column, output the number of ships that exist in-between them. If ships i and j do not belong in the same column, output -1.

Sample Input

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

Sample Output

-1
1

Explanation

Here is an outline of the ship locations throughout the battle:

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 11, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)