E. Ксюша и дерево
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У программиста Ксюши есть дерево, состоящее из n вершин. Будем считать, что вершины дерева пронумерованы от 1 до n. Также будем считать, что первоначально вершина номер 1 покрашена в красный цвет, а остальные вершины покрашены в синий цвет.

Расстоянием между двумя вершинами дерева v и u будем называть количество ребер в кратчайшем пути между v и u.

Ксюше нужно научиться быстро выполнять запросы двух видов:

  1. покрасить заданную синюю вершину в красный цвет;
  2. посчитать, какая красная вершина ближе всего к заданной и вывести кратчайшее расстояние до ближайшей красной вершины.

Ваша задача — написать программу, которая будет выполнять описанные запросы.

Входные данные

В первой строке записаны два целых числа n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — количество вершин в дереве и количество запросов. В следующих n - 1 строках заданы ребра дерева, в i-ой строке записана пара целых чисел ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — очередное ребро дерева.

В следующих m строках заданы запросы. Каждый запрос задан как пара целых чисел ti, vi (1 ≤ ti ≤ 2, 1 ≤ vi ≤ n). Если ti = 1, то в ответ на запрос нужно покрасить синюю вершину vi в красный цвет. Если ti = 2, то в ответ на запрос нужно вывести кратчайшее расстояние от некоторой красной вершины до вершины vi.

Гарантируется, что заданный граф является деревом и что запросы корректны.

Выходные данные

Для каждого запроса второго типа выведите ответ на отдельной строке.

Примеры
Входные данные
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
Выходные данные
0
3
2