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