P1196 [NOI2002] Legend of the Galactic Heroes

In the year $5801$ AD, the inhabitants of Earth migrated to the second planet of Taurus $\alpha$, where they proclaimed the founding of the Galactic Federation. In the same year, the calendar was changed to the Cosmic Era, and expansion toward the depths of the Milky Way began. In Cosmic Era $799$, the two major military groups of the galaxy went to war in the Barmilian starfield. The "Taishan Yading" Group dispatched fleet commander Reinhard with more than $100{,}000$ warships, while the "Qitun Shanhe" Group appointed Yang Wen-li to organize $30{,}000$ warships to meet the enemy.

Yang Wen-li excels at troop deployment and cleverly uses various tactics to win many battles with fewer forces, which inevitably led to some pride. In this decisive battle, he divided the battlefield of the Barmilian starfield into $30000$ columns, numbered $1, 2, \ldots, 30000$ in order. Then, he numbered his warships $1, 2, \ldots, 30000$, placing warship $i$ in column $i$, forming a "single-file long snake" formation to lure the enemy deeper. This is the initial formation. When the invading enemy arrives, Yang will repeatedly issue merge commands to concentrate most of the warships into a few columns for a dense attack. A merge command is `M i j`, meaning the entire warship queue containing warship $i$, as a whole (head at the front and tail at the back), is appended to the tail of the warship queue containing warship $j$. Clearly, a warship queue is composed of one or more warships that are in the same column. Executing a merge command will increase the size of a queue. However, the cunning Reinhard has already taken the strategic initiative. During the battle, through a vast intelligence network, he can eavesdrop on Yang’s fleet maneuver commands at any time. While Yang issues commands to maneuver the fleet, Reinhard will also issue query commands to promptly learn the current distribution of Yang’s warships: `C i j`. This command asks the computer whether Yang’s warships $i$ and $j$ are currently in the same column. If they are in the same column, it asks how many warships are placed between them. As a seasoned senior programmer, you are required to write a program to process Yang’s commands and answer Reinhard’s queries. The decisive battle has begun, and another page in the galaxy’s history has turned.

The first line contains an integer $T$ ($1 \le T \le 5 \times 10^5$), indicating there are $T$ instructions in total. Then follow $T$ lines, each containing one instruction. There are two formats: 1. `M i j`: $i$ and $j$ are two integers ($1 \le i, j \le 30000$), representing the warship IDs involved. This instruction is a fleet maneuver command issued by Yang that Reinhard has intercepted, and it is guaranteed that warships $i$ and $j$ are not in the same column. 2. `C i j`: $i$ and $j$ are two integers ($1 \le i, j \le 30000$), representing the warship IDs involved. This instruction is a query issued by Reinhard. It is guaranteed that in every instruction $i \ne j$.

Process each input instruction in order: - If it is a fleet maneuver command issued by Yang, the fleet formation changes; your program should record the change but must not output anything. - If it is a query issued by Reinhard, output one line containing a single integer: if warships $i$ and $j$ are in the same column, output the number of warships placed strictly between them; otherwise, output $-1$.

Sample explanation Warship position diagram: in the table, Arabic numerals denote warship IDs.  Translated by ChatGPT 5