Фермер Джон заметил, что его коровы чаще спорят, если располагаются слишком близко.
Поэтому он хочет открыть серию новых амбаров и распространить коров по ним.
Всякий раз когда ФД строит новый амбар, он соединяет его не более чем одной
двунаправленной дорожкой с существующим амбаром. Чтобы обеспечить достаточное
удаление коров он иногда хочет определить расстояние от определённого амбара
до самого дальнего амбара достижимого от этого амбара. Расстояние между двумя
амбарами определяется как количество дорожек, по которым нужно пройти от
одного амбара до другого.
ФД имеет \(Q\) (\(1 \leq Q \leq 10^5\)) запросов, каждый вида "построить" или
"расстояние". Для запроса "построить" ФД строит амбар и соединяет его не более
чем с одним из имеющихся амбаров. На запрос "расстояние" ФД спрашивает у Вас
от определённого амбара до самого дальнего амбара достижимого от этого амбара
по некоторой последовательности дорожек. Гарантируется, что амбар запроса уже
построен. Ответьте на запросы ФД.
ФОРМАТ ВВОДА (файл newbarn.in):
Первая строка содержит целое число \(Q\). каждая из последующих \(Q\) строк
содержит запрос. Каждый запрос имеет вид "B p" или "Q k", соответственно
построить амбар и соединить его с амбаром \(p\) или вывести дальнейшее расстояние
по условию задачи от амбара \(k\). Если \(p = -1\), то новый амбар не соединяется
ни с каким из старых. Иначе \(p\) - номер амбара в порядке построения. Амбары
нумеруются от \(1\), т.е. Первый построенный амбар будет иметь номер \(1\), второй
- \(2\), и т.д.
ФОРМАТ ВЫВОДА (файл newbarn.out):
Выведите по одной строке для каждого запроса "расстояние". Заметим, что
амбар, который не соединён ни с одним из других амбаров имеет самое дальнее
расстояние \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2
|
0
2
1
|