Nuovi fienili#10415

Nuovi fienili

1 secondo

128 megabyte

Molto difficile

Il Fattore John ha notato che le sue mucche litigano spesso quando si trovano troppo vicine l'una all'altra, perciò vuole costruire una serie di nuovi fienili per sistemarle più lontano tra loro.

Ogni volta che il Fattore John costruisce un nuovo fienile, lo collega con al più un sentiero bidirezionale a uno dei fienili già esistenti. Per assicurarsi che le mucche siano sistemate abbastanza lontano l'una dall'altra, a volte vuole determinare la distanza da un dato fienile al fienile più lontano raggiungibile da esso (la distanza tra due fienili è il numero di sentieri che bisogna percorrere per andare da un fienile all'altro).

Il Fattore John effettuerà in totale $q$ richieste, ciascuna delle quali è o una richiesta di costruzione o una richiesta di distanza. In una richiesta di costruzione, il Fattore John costruisce un fienile e lo collega con al più uno dei fienili costruiti in precedenza. In una richiesta di distanza, il Fattore John chiede la distanza da un dato fienile al fienile più lontano raggiungibile da esso tramite una sequenza di sentieri. È garantito che il fienile richiesto sia già stato costruito. Aiuta il Fattore John a rispondere a tutte le richieste.

Input

La prima riga contiene un numero intero $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5) — il numero di richieste. Ciascuna delle successive $q$ righe contiene una singola richiesta nella forma B p oppure Q k. La richiesta B p significa che viene costruito un nuovo fienile, collegato al fienile $p$ ; se $p = - 1$ p = -1, il nuovo fienile non viene collegato a nessun altro fienile, altrimenti $p$ è il numero di un fienile già costruito. La richiesta Q k richiede di trovare la distanza dal fienile $k$ al fienile più lontano raggiungibile da esso. I fienili sono numerati a partire da $1$ nell'ordine di costruzione: il primo fienile costruito ha numero $1$ , il secondo ha numero $2$ e così via.

Output

Per ogni richiesta di distanza, stampa la risposta su una riga separata. Nota che per un fienile non collegato a nessun altro fienile, la risposta è $0$ .

Esempi

I dati di input dell'esempio corrispondono alla seguente rete di fienili:

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

Nella richiesta $1$ viene costruito il fienile $1$ . Nella richiesta $2$ viene chiesta la distanza dal fienile $1$ al fienile più lontano raggiungibile. Poiché il fienile $1$ non è collegato a nessun altro fienile, la risposta è $0$ . Nella richiesta $3$ viene costruito il fienile $2$ , collegato al fienile $1$ . Nella richiesta $4$ viene costruito il fienile $3$ , collegato al fienile $2$ . Nella richiesta $5$ viene chiesta la distanza dal fienile $3$ al fienile più lontano raggiungibile. In questo caso il fienile più lontano è il fienile $1$ , che si trova a distanza $2$ . Nella richiesta $6$ viene costruito il fienile $4$ , collegato al fienile $2$ . Nella richiesta $7$ viene chiesta la distanza dal fienile $2$ al fienile più lontano raggiungibile. Tutti e tre i fienili $1$ , $3$ e $4$ si trovano a distanza $1$ da esso, quindi la risposta è $1$ .

Esempio 1