Розробка вакцини

Limits: 2 sec., 256 MiB

Марічка та Зеник — видатні науковці. Уже дуже довго вони розробляють вакцину, що повністю подолає реп’яховірус.

Реп’яховірус складається з молекул та зв’язків між ними. Молекули пронумеровані від 1 до \(n\). Марічка з Зеником з’ясували, що молекули реп’яховірусу формують дерево (зв’язний граф без циклів) з коренем у молекулі 1.

Молекула називається слабкою, якщо вона зв’язана лише з однією іншою молекулою.

Реп’яховірус постійно розвивається: у ньому з’являються нові слабкі молекули, що приєднуються до наявних молекул.

Марічка та Зеник просять вас написати програму, що прискорить розробку вакцини.

Програма повинна обробляти два типи запитів:

• 1 \(v\) — з’являється нова молекула з номером \(m + 1\), що приєднана до молекули \(v\) (тут \(m\) — кількість молекул перед виконанням запиту).

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

Input

У першому рядку задано ціле число \(n\) — початкову кількість молекул у реп’яховірусі.

Кожен з наступних \(n-1\) рядків містить пару цілих чисел — \(a_i\) та \(b_i\), яка означає, що існує зв’язок між відповідними молекулами.

Наступний рядок містить ціле число \(q\) — кількість запитів.

У наступних \(q\) рядках задано запити, по одному на рядок. Кожен запит має вигляд \(t\) \(v\), де \(t\) — тип запиту (1 або 2), а \(v\) — номер молекули. Така молекула гарантовано існує на момент запиту.

Output

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

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le q \le 2 \cdot 10^5\),

є щонайменше один запит другого типу.

Samples

Input (stdin) сopy	Output (stdout) сopy
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\to3\to4\to3\to5\to3\to2\to6\to7\),

Для другого — \(8\to9\to8\to10\).

Для четвертого — \(8\to9\to8\to10\to8\to11\).

Для п’ятого — \(10\).