Muito longe no espaço, em uma certa galáxia, existem $N$ planetas com civilizações desenvolvidas. Os planetas são numerados de $1$ a $N$. Cada planeta administra uma nave espacial. Uma nave está em um de dois estados: em uso para viajar a algum outro planeta ou fora de uso. Quando a nave administrada pelo planeta $a$ está em uso para viajar ao planeta $b$, ela faz repetidas viagens de ida e volta entre $a$ e $b$. Na viagem de $a$ para $b$, passageiros comuns podem embarcar e ir de $a$ para $b$, mas, na viagem de volta de $b$ para $a$, não podem embarcar, por motivos como combustível e transporte de cargas. Quando a nave administrada pelo planeta $a$ está fora de uso, ela permanece no planeta $a$.

Atualmente, todas as naves estão fora de uso. Já foi definido um cronograma de futuras mudanças de estado das naves. Cada mudança é de um dos seguintes tipos.

• Colocar a nave fora de uso administrada pelo planeta $a$ em uso para viajar ao planeta $b$. Isso só ocorre quando passageiros comuns não conseguem ir do planeta $b$ ao planeta $a$ tomando naves algumas vezes.
• Colocar fora de uso a nave em uso administrada pelo planeta $a$.

Duas pessoas que planejam viajar por essa galáxia prepararam algumas perguntas do seguinte formato para planejar seus encontros.

• Em determinado momento do cronograma, suponha que uma pessoa esteja no planeta $a$ e a outra no planeta $b$. Elas conseguem se encontrar usando as naves como passageiros comuns? Se conseguirem, em qual planeta devem se encontrar para minimizar o número de utilizações de naves? Em outras palavras, existe um planeta $c$ ao qual passageiros comuns possam chegar tanto de $a$ quanto de $b$ tomando naves algumas vezes? Se existir, qual planeta $c$ minimiza a soma do número de utilizações de naves para ir de $a$ a $c$ com o número de utilizações para ir de $b$ a $c$?

Você, um excelente programador, recebeu a tarefa de encontrar as respostas para todas as perguntas dessas duas pessoas.

Tarefa

Escreva um programa que responda às perguntas, dados em ordem cronológica o cronograma de futuras mudanças de estado das naves e as perguntas.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $N$, $Q$ separados por um espaço. Eles indicam que há $N$ planetas e que o total de mudanças de estado e perguntas é $Q$.

• As próximas $Q$ linhas representam as mudanças de estado e as perguntas em ordem cronológica. A linha $i$ ($1\le i\le Q$) contém dois ou três inteiros separados por espaços. Chamando o primeiro inteiro de $T_i$, ocorre um dos seguintes casos.

  1. Quando $T_i=1$:

     A linha contém os inteiros $T_i,A_i,B_i$ e representa a seguinte mudança: colocar a nave administrada pelo planeta $A_i$ em uso para viajar ao planeta $B_i$.

     É garantido que $1\le A_i\le N$, $1\le B_i\le N$, $A_i\ne B_i$, que nesse momento a nave administrada pelo planeta $A_i$ está fora de uso e que passageiros comuns não conseguem ir do planeta $B_i$ ao planeta $A_i$ tomando naves algumas vezes.

  2. Quando $T_i=2$:

     A linha contém os inteiros $T_i,A_i$ e representa a seguinte mudança: colocar fora de uso a nave administrada pelo planeta $A_i$.

     É garantido que $1\le A_i\le N$ e que nesse momento a nave administrada pelo planeta $A_i$ está em uso.

  3. Quando $T_i=3$:

     A linha contém os inteiros $T_i,A_i,B_i$ e representa a seguinte pergunta: nesse momento, se uma pessoa estiver no planeta $A_i$ e a outra no planeta $B_i$, elas conseguem se encontrar usando as naves como passageiros comuns? Se conseguirem, em qual planeta devem se encontrar para minimizar o número de utilizações de naves?

     É garantido que $1\le A_i\le N$, $1\le B_i\le N$ e $A_i\ne B_i$.

Saída

Para cada pergunta, escreva na saída padrão, em ordem e em uma linha separada:

• Se as pessoas puderem se encontrar, o número do planeta onde devem se encontrar para minimizar o número de utilizações de naves.
• Se não puderem se encontrar, o inteiro $-1$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Subtarefa 1 [10 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 2 [30 pontos]

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

Subtarefa 3 [60 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

-1
4

Nota

Neste exemplo, as mudanças de estado e as perguntas ocorrem na seguinte ordem.

• A nave administrada pelo planeta $2$ passa a ser usada para viajar ao planeta $4$.
• Nesse momento, se as duas pessoas estiverem nos planetas $2$ e $6$, elas não poderão se encontrar, portanto escrevemos $-1$.
• A nave administrada pelo planeta $4$ passa a ser usada para viajar ao planeta $3$.
• A nave administrada pelo planeta $6$ passa a ser usada para viajar ao planeta $4$.
• Nesse momento, se as duas pessoas estiverem nos planetas $2$ e $6$, elas poderão se encontrar no planeta $3$ ou $4$. Para minimizar o número de utilizações de naves, devem se encontrar no planeta $4$, portanto escrevemos $4$.

Entrada 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

Saída 2

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