Вам задано дерево, состоящее из \(n\) вершин. Первоначально в каждой вершине записано число \(0\).
Вам нужно обработать \(m\) запросов двух видов:
Расстояние между двумя вершинами \(x\) и \(y\) равно количеству ребер на пути из \(x\) в \(y\). Например, расстояние от \(x\) до самой \(x\) равно \(0\).
Расстояние от вершины \(v\) до некоторого пути из \(x\) в \(y\) равно минимуму из расстояний от \(v\) до любой вершины на пути из \(x\) в \(y\).
В первой строке задано одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^5\)) — количество вершин в дереве.
В следующих \(n - 1\) строках заданы ребра дерева — по одному в строке. В каждой строке заданы два целых числа \(u\) и \(v\) (\(1 \le u, v \le n\); \(u \neq v\)) — соответствующее ребро дерева. Гарантируется, что заданные ребра образуют дерево.
В следующей строке задано одно целое число \(m\) (\(1 \le m \le 2 \cdot 10^5\)) — количество запросов.
В следующих \(m\) строках заданы сами запросы — по одному в строке. Каждый запрос имеет один из следующих типов:
Дополнительное ограничение на входные данные: среди запросов есть хотя бы один запрос первого типа.
Для каждого запроса первого типа выведите текущее значение в заданной вершине.
Дерево из первого примера:
6 1 2 1 3 4 2 5 2 3 6 14 2 4 5 10 2 1 3 1 6 2 1 1 10 20 2 6 6 10 20 1 3 2 3 2 10 0 2 5 2 10 1 1 1 1 2 1 3 1 4 1 5 1 6
10 0 30 50 50 40 40 40 20
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач