If you do not wish to read the story, please skip directly to the problem statement.

Three years have passed in the blink of an eye.

The shade of the summer plane trees has replaced the desolation of autumn, framing the backs of LCR and the "God-tier" student (Shenben) as they grow.

The North Gate behind them is no longer the shackle that students once tried to destroy to gain freedom, but a symbol of the memories of their youth.

They have arrived once again at the place where Shenben and LCR first met—under the tree outside the North Gate. This magical tree is no longer in the form of a K-ary tree. At every moment, it manifests life in new and unique ways.

Neither spoke; they watched the natural seeds growing as if by magic. Initially, the tree consisted of only one node, which LCR labeled $1$. Since then, after every interval, a new node has grown from an existing one, and LCR has assigned it a previously unused positive integer label no greater than $n$.

Some sprites live in the tree. They always stay on the nodes. If a sprite is at node $u$, it can jump in one step to any node $v$ such that there is no node $x$ (where $x \neq u$ and $x \neq v$) on the simple path between $u$ and $v$ with a label greater than $\min(u, v)$.

While observing this tree, LCR had some questions. She wanted to know, for a pair of node labels $u$ and $v$, what is the minimum number of steps required to jump from node $u$ to node $v$.

Shenben solved these problems with ease. Eventually, the tree stopped growing, but Shenben remained captivated by it.

An ethereal hand rested on Shenben's shoulder. He turned back and saw LCR smiling.

"My dear boy, Shenben."

"Have you ever wondered why the sprites move according to the laws of my labeling?"

Shenben was speechless for a moment. Suddenly, LCR's hand became illusory, like a flickering torch.

"Your growth is a cross-section of this changing world. Thank you for the time you spent with me. Do not linger... my drifting away is exactly what it means to be with you."

"Goodbye, Shenben."

LCR vanished. Shenben turned around mechanically, only to find that the tree behind him had also disappeared without a trace.

"Shenben, Shenben..." A call came from behind the bewildered Shenben, growing closer and closer. Shenben turned around and found the "noob" LCA from the computer lab running toward him.

"It's graduation season again. Are you okay, senior?"

"Maybe," Shenben looked at the spot where the tree outside the school gate used to be, "LCR is gone, but her shadow will guide our lives."

LCA was silent. He and Shenben looked together at the place where the tree had vanished for a moment.

"So-called 'chuunibyou' fantasies are the only stance for our relatively limited subjective initiative; don't set limits for yourself, LCA. Let us pursue her... pursue the sprites of nature. Perhaps this is our original intention."

This time, it was LCA who watched Shenben's back as he walked further and further away.

"Goodbye, senior."

A certain girls' high school welcomed a new year once again.

So, can you answer the questions posed by LCR?

Problem Statement

For a tree $T=(V, E)$, each node in $V$ has a distinct positive integer label. We denote the node with label $i$ as node $i$.

We define the valley graph of this tree as $G(T)=(V, E')$. $G(T)$ is an undirected simple graph. An edge $(u, v) \in E'$ exists if and only if in $T$, there is no node $x$ (where $x \neq u$ and $x \neq v$) such that $x$ lies on the simple path between $u$ and $v$ and its label is greater than $\min(u, v)$.

There is a tree $T$, initially consisting of only one node with label $1$. There are $q$ operations of the following two types:

• $\texttt{1 u v}$: Add a new node with label $v$ and connect it to the current node with label $u$ (it is guaranteed that no two nodes will ever have the same label).
• $\texttt{2 u v}$: Query the shortest path between node $u$ and node $v$ in $G(T)$ (each edge has a length of $1$).

Please answer all queries.

Input

The first line contains two integers $n$ and $q$, representing the maximum possible label value and the number of operations.

The next $q$ lines each contain three integers $\texttt{op u v}$, describing an operation in the format specified above.

Output

For each operation of type $\texttt{2}$, output one integer per line representing the answer.

Examples

Input 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

Output 1

4
3
2
2

Note 1

The final tree $T$ and $G(T)$ are as follows:

Path for the first query: $1 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 6$;

Path for the second query: $1 \rightarrow 4 \rightarrow 5 \rightarrow 6$;

Path for the third query: $1 \rightarrow 7 \rightarrow 6$;

Path for the fourth query: $3 \rightarrow 5 \rightarrow 6$.

Input 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

Output 2

2
2
1
3
1
2
2
2
2
1
1

Input 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

Output 3

2
3
1
1
1
0
1
3
3
2
0

Subtasks

For all data, $1 \le n \le 10^5, 1 \le q \le 5 \times 10^5$.

The detailed constraints and conventions for each subtask are as follows (a blank cell indicates the same as the general constraints above):

Property I: All $\texttt{1}$ operations (modifications) occur before all $\texttt{2}$ operations (queries).

Property II: The tree is guaranteed to be a path at all times.

Property III: The final tree is chosen uniformly at random from all labeled unrooted trees with $n$ nodes; the random number generator uses the Mersenne Twister.

Note: Example 3 satisfies Properties I and II.