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, \ldots, m\}\);

We define the valley graph of the tree as \(G(T) = (V, E')\). \(G(T)\) is a simple undirected graph on the same vertices as \(T\), and contains an edge \((u, v) \in E'\) 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 \leq n \leq 10^5\).
\(1 \leq q \leq 5 \times 10^5\).

Subtask #	Score	Constraints
1	6	\(n \leq 100\) \(q \leq 200\)
2	10	\(n \leq 5000\) \(q \leq 10000\)
3	12	\(n \leq 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 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 6\).
The shortest path in \(G(T)\) for the second type 2 query is \(1 \rightarrow 4 \rightarrow 5 \rightarrow 6\).
The shortest path in \(G(T)\) for the third type 2 query is \(1 \rightarrow 7 \rightarrow 6\).
One shortest path in \(G(T)\) for the fourth type 2 query is \(3 \rightarrow 5 \rightarrow 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