Корпоративная сеть
Очень большая корпорация развивает свою корпоративную сеть. Вначале каждое из 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 во всех тестовых случаях, с одним числом в каждой - запрашиваемая сумма длин линий, соединяющих соответствующее предприятие с его обслуживающим центром.