우주선

먼 은하에 문명이 발달한 $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$번째 줄에는 공백으로 구분된 정수 2개 또는 3개가 주어집니다. 첫 번째 정수를 $T_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 \ne B_i$이며, 이 시점에 별 $A_i$의 우주선은 사용하지 않는 상태이고, 일반 승객이 그 우주선을 여러 번 타고 $B_i$에서 $A_i$로 갈 수 없습니다.
• $T_i = 2$이면, 이 줄에는 $T_i$, $A_i$가 주어집니다. 별 $A_i$가 관리하는 우주선을 사용하지 않는 상태로 바꿉니다. $1 \le A_i \le N$이며, 이 시점에 별 $A_i$의 우주선은 사용 중입니다.
• $T_i = 3$이면, 이 줄에는 $T_i$, $A_i$, $B_i$가 주어집니다. 이 시점에 한 사람은 별 $A_i$에, 다른 한 사람은 별 $B_i$에 있을 때 두 사람이 합류할 수 있는지 묻는 질문입니다. $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$가 보장됩니다.

각 질문에 대해 순서대로 한 줄씩 출력합니다. 합류할 수 있다면, 우주선 사용 횟수를 가장 적게 만드는 합류 장소의 별 번호를 출력합니다. 합류할 수 없다면 -1을 출력합니다.

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