우주 저 멀리 고도로 발전한 $N$개의 행성이 있는 은하계가 있다. 행성들은 1부터 $N$까지 번호가 매겨져 있다. 각 행성은 하나의 우주선을 관리한다. 우주선은 다른 행성으로 이동하는 데 사용 중인 상태이거나, 사용되지 않는 상태이다. 행성 $a$가 관리하는 우주선이 행성 $b$로 이동하는 데 사용 중인 상태일 때, 이 우주선은 행성 $a$와 행성 $b$ 사이를 여러 번 왕복한다. 우주선이 행성 $a$에서 행성 $b$로 이동할 때는 일반 승객이 우주선에 탑승하여 행성 $a$에서 행성 $b$로 이동할 수 있다. 그러나 우주선이 행성 $b$에서 행성 $a$로 돌아올 때는 연료 문제나 화물 제약으로 인해 일반 승객이 탑승할 수 없다. 또한 행성 $a$가 관리하는 우주선이 사용되지 않는 상태일 때는 행성 $a$에서 대기하고 있다.

현재 모든 우주선은 사용되지 않는 상태이다. 앞으로 우주선의 상태가 어떻게 변할지에 대한 일정이 결정되어 있다. 상태 변화는 다음 두 가지 종류가 있다:

• 현재 사용되지 않는 상태인 행성 $a$가 관리하는 우주선을 행성 $b$로 이동하는 데 사용 중인 상태로 변경한다. 단, 이러한 변경은 일반 승객이 우주선을 여러 번 갈아타서 행성 $b$에서 행성 $a$로 이동하는 것이 불가능할 때만 일어난다.
• 현재 사용 중인 상태인 행성 $a$가 관리하는 우주선을 사용되지 않는 상태로 변경한다.

이 은하계를 여행하려는 두 사람이 만남을 계획하기 위해 다음과 같은 형태의 질문을 여러 개 준비했다:

• 일정의 어느 시점에 한 사람은 행성 $a$에 있고 다른 사람은 행성 $b$에 있다고 가정하자. 두 사람이 일반 승객으로서 우주선을 이용하여 만날 수 있는가? 나아가 만날 수 있다면, 우주선을 이용하는 횟수의 합이 최소가 되도록 하려면 어느 행성에서 만나야 하는가? 즉, 일반 승객이 우주선을 여러 번 탑승하여 행성 $a$에서 행성 $c$로 이동할 수 있고 행성 $b$에서도 행성 $c$로 이동할 수 있는 행성 $c$가 존재하는가? 그러한 행성이 존재한다면, 행성 $a$에서 행성 $c$로 이동하기 위해 우주선을 이용하는 횟수와 행성 $b$에서 행성 $c$로 이동하기 위해 우주선을 이용하는 횟수의 합을 최소화하는 행성 $c$는 어디인가?

뛰어난 프로그래머인 당신은 그들의 모든 질문에 대한 답을 구해 달라는 요청을 받았다.

입력

표준 입력으로부터 다음 입력을 읽어들인다:

• 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $Q$가 주어지며, 이는 각각 행성의 수 $N$과 상태 변화 및 질문의 총 개수 $Q$를 나타낸다.
• 다음 $Q$개의 줄에는 시간 순서대로 일어나는 상태 변화와 질문이 주어진다. $i$번째 줄($1 \le i \le Q$)에는 공백으로 구분된 두 개 또는 세 개의 정수가 주어진다. 첫 번째 정수를 $T_i$라고 하자. 이는 다음 중 하나이다:

(i) $T_i = 1$인 경우: 이 줄에는 정수 $T_i, A_i, B_i$가 주어지며, 이는 다음 상태 변화를 나타낸다: 행성 $A_i$가 관리하는 우주선을 행성 $B_i$로 이동하는 데 사용 중인 상태로 변경한다. $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$이며, 행성 $A_i$가 관리하는 우주선이 현재 사용되지 않는 상태이고, 이 시점에 일반 승객이 우주선을 여러 번 탑승하여 행성 $B_i$에서 행성 $A_i$로 이동하는 것이 불가능함이 보장된다.

(ii) $T_i = 2$인 경우: 이 줄에는 정수 $T_i, A_i$가 주어지며, 이는 다음 상태 변화를 나타낸다: 행성 $A_i$가 관리하는 우주선을 사용되지 않는 상태로 변경한다. $1 \le A_i \le N$이며, 행성 $A_i$가 관리하는 우주선이 현재 사용 중인 상태임이 보장된다.

(iii) $T_i = 3$인 경우: 이 줄에는 정수 $T_i, A_i, B_i$가 주어지며, 이는 다음 질문을 나타낸다: 이 시점에 한 사람이 행성 $A_i$에 있고 다른 사람이 행성 $B_i$에 있다면, 두 사람이 일반 승객으로서 우주선을 이용하여 만날 수 있는가? 만날 수 있다면 우주선 이용 횟수를 최소화하는 행성 $c$는 어디인가? $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$임이 보장된다.

출력

각 질문에 대해 표준 출력의 새로운 줄에 다음을 출력하라:

• 만날 수 있다면, 우주선 이용 횟수를 최소화하기 위해 만나야 하는 행성의 번호.
• 만날 수 없다면, 정수 -1.

제한

모든 입력 데이터는 다음 조건을 만족한다:

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

서브태스크

서브태스크 1 [10점]

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

서브태스크 2 [30점]

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

서브태스크 3 [60점]

• 추가적인 제한 조건이 없다.

예제

입력 1

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

출력 1

-1
4

참고 1

이 예제에서 상태 변화와 질문은 다음 순서로 일어난다:

• 행성 2가 관리하는 우주선이 행성 4로 이동하는 데 사용 중인 상태가 된다.
• 이 시점에 두 사람이 행성 2와 행성 6에 있다면 만날 수 없으므로 -1을 출력한다.
• 행성 4가 관리하는 우주선이 행성 3으로 이동하는 데 사용 중인 상태가 된다.
• 행성 6이 관리하는 우주선이 행성 4로 이동하는 데 사용 중인 상태가 된다.
• 이 시점에 두 사람이 행성 2와 행성 6에 있다면 행성 3 또는 행성 4에서 만날 수 있다. 우주선 이용 횟수를 최소화하려면 행성 4에서 만나야 하므로 4를 출력한다.

입력 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

출력 2

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