Розробка вакцини
Limits: 2 sec., 256 MiB
Марічка та Зеник — видатні науковці. Уже дуже довго вони розробляють вакцину, що повністю подолає реп’яховірус.
Реп’яховірус складається з молекул та зв’язків між ними. Молекули пронумеровані від 1 до n. Марічка з Зеником з’ясували, що молекули реп’яховірусу формують дерево (зв’язний граф без циклів) з коренем у молекулі 1.
Молекула називається слабкою, якщо вона зв’язана лише з однією іншою молекулою.
Реп’яховірус постійно розвивається: у ньому з’являються нові слабкі молекули, що приєднуються до наявних молекул.
Марічка та Зеник просять вас написати програму, що прискорить розробку вакцини.
Програма повинна обробляти два типи запитів:
1v — з’являється нова молекула з номером m+1, що приєднана до молекули v (тут m — кількість молекул перед виконанням запиту).2v — знайти довжину найкоротшого шляху (необов’язково простого), що починається в молекулі v та проходить через усі слабкі молекули в піддереві цієї молекули. Довжиною шляху називається кількість ребер (зв’язків) у цьому шляху.
Input
У першому рядку задано ціле число n — початкову кількість молекул у реп’яховірусі.
Кожен з наступних n−1 рядків містить пару цілих чисел — ai та bi, яка означає, що існує зв’язок між відповідними молекулами.
Наступний рядок містить ціле число q — кількість запитів.
У наступних q рядках задано
запити, по одному на рядок. Кожен запит має вигляд t v,
де t — тип запиту (1
або 2), а v — номер
молекули. Така молекула гарантовано існує на момент запиту.
Output
Для кожного запиту другого типу виведіть рядок, що містить ціле число — відповідь на цей запит.
Constraints
1≤n≤2⋅105,
1≤q≤2⋅105,
є щонайменше один запит другого типу.
Samples
| Input (stdin) | Output (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 |
Notes
Для першого запиту оптимальний шлях — 2→3→4→3→5→3→2→6→7,
Для другого — 8→9→8→10.
Для четвертого — 8→9→8→10→8→11.
Для п’ятого — 10.