It's Christmas time and Leonard has bought a small Christmas tree and placed right in the center of hall. Seeing the tree, Sheldon remembers that he has to solve a graph problem.

The problem states that given a tree graph, initially containing just one node labeled 1. There are Q queries, each one being one of following two types--

• 1 p - You must connect a node to node with label p. The label of this new node will be the minimum label which is not currently present in the tree.
• 2 - You must output the maximum possible distance between a pair of nodes u and v of the tree. Distance between nodes u and v is the number of edges on the unique path from node u to node v.

Input Format:

First line contains Q, number of queries.

Each of the next Q lines denote a query. if it starts with 1, it is of type 1 and another integer p follows. If it starts with 2, it denotes the query of type 2.

Output Format:

Output the required answer for each query of type 2.

Constraints:

$1 \leq Q \leq 10^5$

$1 \leq p \leq$ max label currently in the tree