Запити на дереві
Limits: 5 sec., 512 MiB
Зеник і Марічка мають дерево (зв’язаний ациклічний неорієнтований граф) із \(n\) вершин. Початково усі вершини пофарбовано у білий колір.
Вони хочуть навчитись опрацьовувати запити двох типів:
1 \(v\) — пофарбувати \(v\)-ту вершину у чорний колір. Зауважте, що вершина могла бути пофарбованою в чорний колір раніше, в такому разі колір не змінюється.
2 \(v\) — знайти та вивести відстань (кількість ребер) від вершини \(v\) до найближчої чорної вершини. Якщо чорних вершин немає, потрібно вивести -1.
Допоможіть їм опрацювати задану послідовність із \(m\) запитів.
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість вершин та запитів відповідно.
У наступних \(n-1\) рядках задано пари цілих чисел \(u_i\) та \(v_i\), розділених пробілами — ребра дерева. Вершини пронумеровані цілими числами від 1 до \(n\) включно.
У наступних \(m\) рядках задано запити, по одному запиту на рядок, у форматі, описаному в умові.
Output
У одному рядку для кожного запиту другого типу виведіть одне ціле число через пробіл — відповідь на відповідний запит.
Constraints
\(1 \le n, m \le 10^5\),
\(1 \le u_i, v_i \le n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 8 8 2 4 1 2 7 6 7 5 8 7 3 4 4 7 2 3 1 5 2 8 2 1 1 4 2 1 2 7 2 6 | -1 2 4 2 1 2 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|