Розробка вакцини
Обмеження: 2 сек., 256 МіБ
Марічка та Зеник — видатні науковці. Уже дуже довго вони розробляють вакцину, що повністю подолає реп’яховірус.
Реп’яховірус складається з молекул та зв’язків між ними. Молекули пронумеровані від 1 до nn. Марічка з Зеником з’ясували, що молекули реп’яховірусу формують дерево (зв’язний граф без циклів) з коренем у молекулі 1.
Молекула називається слабкою, якщо вона зв’язана лише з однією іншою молекулою.
Реп’яховірус постійно розвивається: у ньому з’являються нові слабкі молекули, що приєднуються до наявних молекул.
Марічка та Зеник просять вас написати програму, що прискорить розробку вакцини.
Програма повинна обробляти два типи запитів:
1vv — з’являється нова молекула з номером m+1m+1, що приєднана до молекули vv (тут mm — кількість молекул перед виконанням запиту).2vv — знайти довжину найкоротшого шляху (необов’язково простого), що починається в молекулі vv та проходить через усі слабкі молекули в піддереві цієї молекули. Довжиною шляху називається кількість ребер (зв’язків) у цьому шляху.
Вхідні дані
У першому рядку задано ціле число nn — початкову кількість молекул у реп’яховірусі.
Кожен з наступних n−1n−1 рядків містить пару цілих чисел — aiai та bibi, яка означає, що існує зв’язок між відповідними молекулами.
Наступний рядок містить ціле число qq — кількість запитів.
У наступних qq рядках задано
запити, по одному на рядок. Кожен запит має вигляд tt vv,
де tt — тип запиту (1
або 2), а vv — номер
молекули. Така молекула гарантовано існує на момент запиту.
Вихідні дані
Для кожного запиту другого типу виведіть рядок, що містить ціле число — відповідь на цей запит.
Обмеження
1≤n≤2⋅1051≤n≤2⋅105,
1≤q≤2⋅1051≤q≤2⋅105,
є щонайменше один запит другого типу.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 10 1 2 2 3 3 5 3 4 2 6 6 7 1 8 8 9 8 10 5 2 2 2 8 1 8 2 8 2 10 | 8 3 5 0 |
Примітки
Для першого запиту оптимальний шлях — 2→3→4→3→5→3→2→6→72→3→4→3→5→3→2→6→7,
Для другого — 8→9→8→108→9→8→10.
Для четвертого — 8→9→8→10→8→118→9→8→10→8→11.
Для п’ятого — 1010.