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 4322

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 22131222211

 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 23111013320

Submitting .cpp to 'gate'

Time Limit: 3 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: LOJ #2474