CORNET - Corporative Network

## 题目描述 原本有 $n$ 个节点，最初每个节点的父亲都是自己。 现在给你若干操作，共分为两种，操作格式如下： 1. `I x y`（大写字母`I`） 将 $x$ 的父亲变为 $y$，而且令 $x$ 与 $y$ 之间的距离为 $\lvert x-y \rvert \bmod 1000$。 2. `E x` 询问x点到其根节点的距离 数据保证对于所有的 $1$ 操作合法，即保证之前 $y$ 不是 $x$ 的父亲、 ## 输入格式 第一行输入一个整数 $T$，表示每个数据点的数据组数。 接下来对于每组数据输入格式如下： 第一行包含一个正整数 $n$，表示原有的节点个数 从第二行开始，以下有若干行，每一行的输入格式为 `I x y` 或`E x` 分别代表以上的两种操作 对于这些操作，以输入一个`O`（大写字母`O`）为终止。 ## 输出格式 一共若干行，表示对于每一组测试数据中的 `E` 操作输出答案。

A very big corporation is developing its corporate network. At the beginning, each of the **N** enterprises of the corporation, numbered from 1 to **N**, organized its own computing and telecommunication center. Soon, for amelioration of the services, the corporation started to collect some enterprises in clusters, each of them served by a single computing and telecommunication center as follows. The corporation chose one of the existing centers **I** (serving the cluster **A**) and one of the enterprises **J** in some other cluster **B** (not necessarily the center) and linked them with a telecommunication line. The length of the line between the enterprises **I** and **J** is |**I** – **J**|(mod 1000). In such a way two old clusters are joined to form a new cluster, served by the center of the old cluster **B**. Unfortunately after each join the sum of the lengths of the lines linking an enterprise to its serving center could be changed and the end users would like to know what is the new length. Write a program to keep trace of the changes in the organization of the network that is able at each moment to answer the questions of the users.

The first line of the input file will contains only the number **T** of the test cases (1 <= **T** <= 5). Each test will start with the number **N** of enterprises (5<=**N**<=20000). Then some number of lines (no more than 200000) will follow with one of the commands: **E I**– asking the length of the path from the enterprise **I** to its serving center at the moment; **I I J** – informing that the serving center **I** is linked to the enterprise **J**. The test case finishes with a line containing the word **O**. There are fewer **I** commands than **N** commands.

The output should contain as many lines as the number of **E** commands in all test cases. Each line must contain a single number – the requested sum of lengths of lines connecting the corresponding enterprise with its serving center.

1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O

0
2
3
5