Spaceships

Far away in a galaxy, there are $N$ civilized stars numbered 1 through $N$. Each star manages one spaceship. A spaceship is either in use, traveling to some other star, or idle. If the spaceship managed by star $a$ is in use and heading to star $b$, it shuttles between stars $a$ and $b$ many times. When the spaceship goes from star $a$ to star $b$, ordinary passengers can ride it from $a$ to $b$. When it returns from $b$ to $a$, however, ordinary passengers cannot board it, because of fuel issues, cargo loading, and similar reasons. While the spaceship managed by star $a$ is idle, it waits at star $a$.

All spaceships are idle now. The schedule of future status changes is already set. Each change is one of the following two kinds.

• An idle spaceship managed by star $a$ is set to in use, heading to star $b$. This is done only when ordinary passengers cannot ride that spaceship several times to go from $b$ to $a$.
• An in-use spaceship managed by star $a$ is set to idle.

Two people planning a trip through this galaxy prepare several questions to decide where to meet. At some moment, one person is at star $a$ and the other is at star $b$. Can the two of them meet as ordinary passengers using the spaceships? If they can, which star gives the fewest spaceship uses? In other words, does a star $c$ exist such that ordinary passengers can ride spaceships several times to get from $a$ to $c$ and from $b$ to $c$? If it exists, which star $c$ minimizes the sum of the number of spaceship uses needed to go from $a$ to $c$ and the number needed to go from $b$ to $c$?

The first line contains two integers $N$ and $Q$ separated by a space. $N$ is the number of stars, and $Q$ is the total number of status changes and questions.

The following $Q$ lines describe the status changes and questions in chronological order. Line $i$ contains two or three integers separated by spaces. Let $T_i$ be the first integer. Then one of the following holds.

• If $T_i = 1$, the line contains $T_i$, $A_i$, $B_i$. The spaceship managed by star $A_i$ is set to in use, heading to star $B_i$. It is guaranteed that $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$, that this spaceship is idle at this moment, and that ordinary passengers cannot ride it several times to go from $B_i$ to $A_i$ at this moment.
• If $T_i = 2$, the line contains $T_i$, $A_i$. The spaceship managed by star $A_i$ is set to idle. It is guaranteed that $1 \le A_i \le N$ and that this spaceship is in use at this moment.
• If $T_i = 3$, the line contains $T_i$, $A_i$, $B_i$. This is a question: at this moment, one person is at star $A_i$ and the other is at star $B_i$. It is guaranteed that $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$.

For each question, in order, print one line. If the two can meet, print the number of the star where they should meet to minimize the number of spaceship uses. If they cannot meet, print -1.

• $2 \le N \le 1000000$
• $1 \le Q \le 1000000$