У программиста Ксюши есть дерево, состоящее из n вершин. Будем считать, что вершины дерева пронумерованы от 1 до n. Также будем считать, что первоначально вершина номер 1 покрашена в красный цвет, а остальные вершины покрашены в синий цвет.
Расстоянием между двумя вершинами дерева v и u будем называть количество ребер в кратчайшем пути между v и u.
Ксюше нужно научиться быстро выполнять запросы двух видов:
- покрасить заданную синюю вершину в красный цвет;
- посчитать, какая красная вершина ближе всего к заданной и вывести кратчайшее расстояние до ближайшей красной вершины.
Ваша задача — написать программу, которая будет выполнять описанные запросы.
Выходные данные
Для каждого запроса второго типа выведите ответ на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
|
0
3
2
|