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:
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 one line for each query of type 2  containing a single integer, the shortest path in \(G(T)\) between the queried vertices.
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 
Sample Input 1  Sample Output 1 
7 10

4

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

2

Sample Input 3  Sample Output 3 
10 20

2

Subtask  Score 

1  6 
2  10 
3  12 
4  15 
5  12 
6  20 
7  25 
8  0 