Nuevos establos#10415

Nuevos establos

1 segundo

128 megabytes

Muy difícil

El granjero Juan se ha dado cuenta de que sus vacas a menudo se pelean cuando están demasiado cerca unas de otras, por lo que quiere construir una serie de nuevos establos para separarlas más.

Cada vez que el granjero Juan construye un nuevo establo, lo conecta con, como máximo, un camino bidireccional a uno de los establos ya existentes. Para asegurarse de que las vacas estén lo suficientemente separadas entre sí, a veces quiere determinar la distancia desde un establo dado hasta el establo más alejado al que se puede llegar desde él (la distancia entre dos establos es la cantidad de caminos que hay que recorrer para llegar de un establo a otro).

El granjero Juan realizará un total de $q$ consultas, cada una de las cuales es una consulta de construcción o una consulta de distancia. En una consulta de construcción, el granjero Juan construye un establo y lo conecta con, como máximo, un establo previamente construido. En una consulta de distancia, el granjero Juan pregunta la distancia desde un establo dado hasta el establo más alejado al que se puede llegar desde él mediante una secuencia de caminos. Se garantiza que el establo consultado ya ha sido construido. Ayuda al granjero Juan a responder todas las consultas.

Entrada

La primera línea contiene un número entero $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5) — la cantidad de consultas. Cada una de las siguientes $q$ líneas contiene una consulta de la forma B p o Q k. La consulta B p significa que se construye un nuevo establo, el cual se conecta con el establo $p$ ; si $p = - 1$ p = -1, entonces el nuevo establo no se conecta con ningún otro establo, de lo contrario $p$ es el número de un establo ya construido. La consulta Q k requiere hallar la distancia desde el establo $k$ hasta el establo más alejado al que se puede llegar desde él. Los establos se numeran desde $1$ en el orden en que fueron construidos: el primer establo construido tiene el número $1$ , el segundo el número $2$ , y así sucesivamente.

Salida

Para cada consulta de distancia, muestra la respuesta en una línea aparte. Ten en cuenta que para un establo que no está conectado con ningún otro establo, la respuesta es $0$ .

Ejemplos

Los datos de entrada del ejemplo corresponden a la siguiente red de establos:

  (1)
    \
     (2)---(4)
    /
  (3)

En la consulta $1$ se construye el establo $1$ . En la consulta $2$ se pregunta la distancia desde el establo $1$ hasta el establo más alejado al que se puede llegar. Dado que el establo $1$ no está conectado con ningún otro establo, la respuesta es $0$ . En la consulta $3$ se construye el establo $2$ , el cual se conecta con el establo $1$ . En la consulta $4$ se construye el establo $3$ , el cual se conecta con el establo $2$ . En la consulta $5$ se pregunta la distancia desde el establo $3$ hasta el establo más alejado al que se puede llegar. En este caso, el más alejado es el establo $1$ , que se encuentra a una distancia de $2$ . En la consulta $6$ se construye el establo $4$ , el cual se conecta con el establo $2$ . En la consulta $7$ se pregunta la distancia desde el establo $2$ hasta el establo más alejado al que se puede llegar. Los tres establos $1$ , $3$ y $4$ están a una distancia de $1$ de él, por lo que la respuesta es $1$ .

Ejemplo 1