Нові корівники#10415

Нові корівники

1 секунда

128 мегабайтів

Дуже складна

Фермер Джон помітив, що його корови часто сваряться, коли знаходяться занадто близько одна до одної, тому він хоче побудувати ряд нових корівників, щоб розселити їх подалі.

Кожного разу, коли Фермер Джон будує новий корівник, він з'єднує його не більш як однією двосторонньою стежкою з одним із уже існуючих корівників. Щоб переконатися, що корови розселені достатньо далеко одна від одної, він іноді хоче визначити відстань від заданого корівника до найвіддаленішого корівника, досяжного з нього (відстань між двома корівниками — це кількість стежок, які потрібно пройти, щоб дістатися від одного корівника до іншого).

Фермер Джон зробить загалом $q$ запитів, кожен з яких є або запитом на побудову, або запитом відстані. У запиті на побудову Фермер Джон будує корівник і з'єднує його не більш як з одним раніше побудованим корівником. У запиті відстані Фермер Джон запитує відстань від заданого корівника до найвіддаленішого корівника, досяжного з нього за послідовністю стежок. Гарантується, що запитуваний корівник уже побудований. Допоможіть Фермеру Джону відповісти на всі запити.

Вхідні дані

Перший рядок містить ціле число $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5) — кількість запитів. Кожен з наступних $q$ рядків містить один запит вигляду B p або Q k. Запит B p означає, що будується новий корівник, який з'єднується з корівником $p$ ; якщо $p = - 1$ p = -1, то новий корівник не з'єднується з жодним іншим корівником, інакше $p$ — номер уже побудованого корівника. Запит Q k вимагає знайти відстань від корівника $k$ до найвіддаленішого корівника, досяжного з нього. Корівники нумеруються з $1$ у порядку побудови: перший побудований корівник має номер $1$ , другий — номер $2$ і так далі.

Вихідні дані

Для кожного запиту відстані виведіть відповідь в окремому рядку. Зауважте, що для корівника, не з'єднаного з жодним іншим корівником, відповідь дорівнює $0$ .

Приклади

Вхідні дані з прикладу відповідають такій мережі корівників:

  (1)
    \
     (2)---(4)
    /
  (3)

У запиті $1$ будується корівник $1$ . У запиті $2$ запитується відстань від корівника $1$ до найвіддаленішого досяжного корівника. Оскільки корівник $1$ не з'єднаний з жодним іншим корівником, відповідь дорівнює $0$ . У запиті $3$ будується корівник $2$ , який з'єднується з корівником $1$ . У запиті $4$ будується корівник $3$ , який з'єднується з корівником $2$ . У запиті $5$ запитується відстань від корівника $3$ до найвіддаленішого досяжного корівника. У цьому випадку найвіддаленішим є корівник $1$ , що знаходиться на відстані $2$ . У запиті $6$ будується корівник $4$ , який з'єднується з корівником $2$ . У запиті $7$ запитується відстань від корівника $2$ до найвіддаленішого досяжного корівника. Усі три корівники $1$ , $3$ і $4$ знаходяться від нього на відстані $1$ , тому відповідь дорівнює $1$ .

Приклад 1