gate

After the North Gate

Given a tree $T=(V,E)$ with $n$ vertices $V$ and $n-1$ edges $E$, in which the vertices have distinct but not necessarily consecutive indices $V\subseteq \{1,2,\dots ,m\}$;

We define the valley graph of the tree as $G(T)=(V,E^{\prime })$. $G(T)$ is a simple undirected graph on the same vertices as $T$, and contains an edge $(u,v)\in E^{\prime }$ if and only if the simple path between $u$ and $v$ in $T$ contains no other vertices with index greater than $min(u,v)$.

Let us construct a tree $T$. Initially, the tree will contain only a single vertex with index $1$. $q$ queries are then to be performed:

• $1$ $u$ $v$: Add a new vertex with index $v$ to $T$, and construct an edge between it and an existing vertex $u$.
• $2$ $u$ $v$: Find the length of the shortest path between vertices $u$ and $v$ in the valley graph $G(T)$.

Your task is to answer the queries of type 2, as described above.

Input format

The first line of input consists of two integers $n$ and $q$, indicating the maximum index of a vertex and the number of queries.
$q$ lines of input follow. Each line will contain 3 integers following one of the query formats.

Output format

Output one line for each query of type 2 - containing a single integer, the shortest path in $G(T)$ between the queried vertices.

Limits

$1\le n\le {10}^5$.
$1\le q\le 5\times {10}^5$.

Subtask #	Score	Constraints
1	6	$n\le 100$ $q\le 200$
2	10	$n\le 5000$ $q\le 10000$
3	12	$n\le 5000$
4	15	All type 1 queries occur before all type 2 queries. The tree $T$ forms a line graph at all points in time.
5	12	The tree $T$ forms a line graph at all points in time.
6	20	All type 1 queries occur before all type 2 queries.
7	25	No additional constraints

Samples

Sample Input 1	Sample Output 1
7 10 1 1 2 1 2 3 1 3 5 1 5 6 2 1 6 1 1 4 2 1 6 1 1 7 2 1 6 2 3 6	4 3 2 2

In this sample input, the final layouts of the tree $T$ and its valley graph $G(T)$ are respectively:

The shortest path in $G(T)$ for the first type 2 query is $1\to 2\to 3\to 5\to 6$.
The shortest path in $G(T)$ for the second type 2 query is $1\to 4\to 5\to 6$.
The shortest path in $G(T)$ for the third type 2 query is $1\to 7\to 6$.
One shortest path in $G(T)$ for the fourth type 2 query is $3\to 5\to 6$.

Sample Input 2	Sample Output 2
10 20 1 1 8 1 8 5 1 5 10 1 8 7 2 7 1 1 7 4 2 7 5 1 7 6 2 7 6 1 6 9 2 4 1 1 9 2 2 8 1 1 9 3 2 3 10 2 6 8 2 4 8 2 3 8 2 3 9 2 8 1	2 2 1 3 1 2 2 2 2 1 1

Sample Input 3	Sample Output 3
10 20 1 1 7 1 7 6 1 1 2 1 6 4 1 2 3 1 3 5 1 5 9 1 9 8 1 8 10 2 7 10 2 8 3 2 9 5 2 1 7 2 2 1 2 9 9 2 2 7 2 4 3 2 5 4 2 9 2 2 1 1	2 3 1 1 1 0 1 3 3 2 0