Far away in the universe, there is a galaxy with $N$ advanced planets. The planets are numbered from 1 to $N$. Each planet manages one spaceship. A spaceship is either in a state of being used to travel to another planet, or in an unused state. When the spaceship managed by planet $a$ is in the state of being used to travel to planet $b$, the spaceship is traveling back and forth between planet $a$ and planet $b$ many times. When the spaceship travels from planet $a$ to planet $b$, general passengers can board the spaceship to travel from planet $a$ to planet $b$. However, when the spaceship returns from planet $b$ to planet $a$, general passengers cannot board due to fuel issues or cargo constraints. Also, when the spaceship managed by planet $a$ is in the unused state, it is waiting at planet $a$.

Currently, all spaceships are in the unused state. A schedule for future changes in the state of the spaceships has been determined. The state changes are of the following types:

• Change the spaceship managed by planet $a$ (which is currently in the unused state) to the state of being used to travel to planet $b$. Note that this only occurs when it is impossible for general passengers to travel from planet $b$ to planet $a$ by boarding spaceships multiple times.
• Change the spaceship managed by planet $a$ (which is currently in the used state) to the unused state.

Two people planning to travel through this galaxy have prepared several questions of the following form to plan their meeting:

• At a certain point in the schedule, suppose one person is at planet $a$ and the other is at planet $b$. Can the two people meet by using spaceships as general passengers? Furthermore, if they can meet, at which planet would they meet such that the number of times they use a spaceship is minimized? That is, does there exist a planet $c$ such that general passengers can travel from planet $a$ to planet $c$ and from planet $b$ to planet $c$ by boarding spaceships multiple times? If such a planet exists, which planet $c$ minimizes the sum of the number of times a spaceship is used to travel from planet $a$ to planet $c$ and the number of times a spaceship is used to travel from planet $b$ to planet $c$?

You, an excellent programmer, have been asked to find the answers to all of their questions.

Input

Read the following from standard input:

• The first line contains two integers $N$ and $Q$, separated by a space, representing the number of planets $N$, and the total number of state changes and questions $Q$.
• The following $Q$ lines represent the state changes and questions in chronological order. The $i$-th line ($1 \le i \le Q$) contains two or three integers separated by spaces. Let the first integer be $T_i$. It is one of the following:

(i) If $T_i = 1$: This line contains integers $T_i, A_i, B_i$, representing the following state change: change the spaceship managed by planet $A_i$ to the state of being used to travel to planet $B_i$. It is guaranteed that $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$, that the spaceship managed by planet $A_i$ is currently in the unused state, and that at this moment, it is impossible for general passengers to travel from planet $B_i$ to planet $A_i$ by boarding spaceships multiple times.

(ii) If $T_i = 2$: This line contains integers $T_i, A_i$, representing the following state change: change the spaceship managed by planet $A_i$ to the unused state. It is guaranteed that $1 \le A_i \le N$, and that the spaceship managed by planet $A_i$ is currently in the used state.

(iii) If $T_i = 3$: This line contains integers $T_i, A_i, B_i$, representing the following question: at this moment, if one person is at planet $A_i$ and the other is at planet $B_i$, can they meet by using spaceships as general passengers? If they can meet, which planet $c$ minimizes the number of spaceship uses? It is guaranteed that $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$.

Output

For each question, output the following to standard output on a new line:

• If they can meet, the number of the planet where they should meet to minimize the number of spaceship uses.
• If they cannot meet, the integer -1.

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 1\,000\,000$.
• $1 \le Q \le 1\,000\,000$.

Subtasks

Subtask 1 [10 points]

• $N \le 5\,000$.
• $Q \le 5\,000$.

Subtask 2 [30 points]

• $T_i \neq 2$ ($1 \le i \le Q$).

Subtask 3 [60 points]

• No additional constraints.

Examples

Input 1

6 5
1 2 4
3 2 6
1 4 3
1 6 4
3 2 6

Output 1

-1
4

Note 1

In this example, the state changes and questions occur in the following order:

• The spaceship managed by planet 2 enters the state of being used to travel to planet 4.
• At this point, if two people are at planet 2 and planet 6, they cannot meet, so output -1.
• The spaceship managed by planet 4 enters the state of being used to travel to planet 3.
• The spaceship managed by planet 6 enters the state of being used to travel to planet 4.
• At this point, if two people are at planet 2 and planet 6, they can meet at planet 3 or planet 4. To minimize the number of spaceship uses, they should meet at planet 4, so output 4.

Input 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

Output 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6