Country A plans to build a new tree-structured transportation network. This network can be described as a tree $T$. The transportation network $T$ has $n$ nodes and exactly $n-1$ bidirectional roads connecting these nodes, such that all nodes are connected. The maximum distance between any two nodes in the network is called the diameter of the network.

Country B, an enemy of Country A, has sent a spy to secretly tamper with Country A's network construction plan. To avoid detection, the spy can perform at most one modification to the network, where this modification consists of swapping the connection targets of two roads in the network. That is, the spy can choose two different roads, say one originally connecting $x_1, y_1$ and the other connecting $x_2, y_2$, and modify them such that one road now connects $x_1, y_2$ and the other connects $x_2, y_1$, while ensuring that the resulting transportation network remains a tree. The spy's goal is to modify the network to make the diameter of the transportation network built by Country A as large as possible. Country A's network construction plan is constantly being adjusted, and the spy cannot make direct modifications for the time being. However, to be able to tamper with the plan at any time, the spy needs to know the current optimal tampering strategy after each network adjustment.

Implementation Details

Given Country A's current network construction plan, calculate the maximum diameter of the transportation network after the optimal tampering.

Input

The first line contains a positive integer $n$, representing the number of adjustments. The transportation network initially has only one node, the capital of Country A, labeled 1. The next $n$ lines each contain two positive integers $opt, x$, describing each adjustment in sequence. Here, $opt$ is either 1 or 2. If $opt = 1$, it means a new node has been added to the transportation network, and there is an edge between it and node $x$. It is guaranteed that $x$ is an existing node. The node added in the $i$-th adjustment is labeled $i+1$. If $opt = 2$, it means node $x$ and all edges connected to it are removed from the network. Node 1 will never be removed, and it is guaranteed that the transportation network remains a tree after each adjustment.

Constraints

• For 30% of the data, $n \le 5000$.
• For 80% of the data, $n \le 50000$.
• For 100% of the data, $n \le 200000$.

Output

Output $n$ lines, each containing an integer, representing the maximum diameter of the transportation network if at most one modification is performed after each adjustment.

Examples

Input 1

5
1 1
1 2
1 3
2 4
1 2

Output 1

1
2
3
2
2