Корпоративна мережа
Дуже велика корпорація розширює свою корпоративну мережу. Спочатку кожне з N підприємств корпорації, пронумерованих від 1 до N, мало власний обчислювальний та телекомунікаційний центр. Згодом, для покращення послуг, корпорація почала об'єднувати деякі підприємства в кластери, кожен з яких обслуговується єдиним обчислювальним та телекомунікаційним центром. Це відбувається наступним чином: корпорація обирає один з існуючих центрів I (який обслуговує кластер A) та одне з підприємств J в іншому кластері B (не обов'язково центр) і з'єднує їх телекомунікаційною лінією. Довжина лінії між підприємствами I та J дорівнює |I – J|(mod 1000). Таким чином, два старих кластери об'єднуються в новий кластер, який обслуговується центром старого кластера B. На жаль, після кожного об'єднання сума довжин ліній, що з'єднують підприємство з його обслуговуючим центром, може змінюватися, і кінцеві користувачі хотіли б знати, якою є нова довжина. Напишіть програму, яка відстежує зміни в організації мережі та здатна в будь-який момент відповідати на запитання користувачів.
Вхідні дані
Ваша програма повинна бути готова вирішувати більше ніж один тестовий випадок. Перша строка вхідних даних містить лише число T тестових випадків. Кожен тест починається з числа N підприємств (5 ≤ N ≤ 20000). Потім слідує деяка кількість рядків (не більше 200000) з однією з команд:
E I - запит про довжину шляху від підприємства I до його обслуговуючого центру на даний момент;
I I J - повідомлення, що обслуговуючий центр I з'єднаний з підприємством J.
Тестовий випадок закінчується рядком, що містить слово O. Команд I менше ніж N.
Вихідні дані
Вихідні дані повинні містити стільки рядків, скільки команд E у всіх тестових випадках, з одним числом у кожному - запитувана сума довжин ліній, що з'єднують відповідне підприємство з його обслуговуючим центром.