Copiado al portapapeles
Descripción
Rondo el programador tiene un árbol que consta de n nodos. Consideraremos los nodos de árbol indexados de 1 a n. También consideraremos que el primer nodo se pintará inicialmente de rojo, y los otros nodos, se pintarán de azul.
La distancia entre dos nodos de árbol v y u es el número de aristas en la ruta más corta entre v y u.
Rondo necesita aprender a ejecutar consultas de dos tipos:
1) Pintar un nodo azul en rojo.
2) Calcular qué nodo rojo es el más cercano a un nodo dado e imprima la distancia más corta al nodo rojo más cercano.
Su tarea es escribir un programa que ejecute las consultas descritas.
Entrada
La entrada consiste en un solo caso de entrada por prueba.
La primera línea contiene dos enteros n y m $(2 \leq n \leq 10^4, 1 \leq m \leq 10^4)$: el número de nodos en el árbol y el número de consultas. Las siguientes n - 1 líneas contienen los bordes del árbol, la línea i-ésima contiene un par de enteros $a_i, b_i (1 \leq a_i, b_i \leq n, a_i \neq b_i)$ - un borde del árbol.
Las siguientes m líneas contienen consultas. Cada consulta se especifica como un par de enteros $t_i, v_i (1 \leq t_i \leq 2, 1 \leq v_i \leq n)$. Si $t_i = 1$, entonces como respuesta a la consulta necesitamos pintar un nodo azul $v_i$ en rojo. Si $t_i = 2$, entonces deberíamos responder a la consulta imprimiendo la distancia más corta desde algún nodo rojo al nodo $v_i$.
Se garantiza que el grafo es un árbol y que todas las consultas son correctas.
Salida
Para cada consulta de tipo 2) Imprima la respuesta en una sola línea.
Ejemplo Entrada
5 4 1 2 2 3 2 4 4 5 2 1 2 5 1 2 2 5
Ejemplo Salida
0 3 2