Dans une galaxie située aux confins de l'Univers, $N$ astres abritent des civilisations avancées. Ces astres sont numérotés de $1$ à $N$. Chacun gère un vaisseau spatial. Un vaisseau est soit en service pour se rendre vers un autre astre, soit hors service. Lorsque le vaisseau géré par l'astre $a$ est en service à destination de l'astre $b$, il effectue des allers-retours répétés entre $a$ et $b$. Lorsqu'il va de $a$ vers $b$, les passagers ordinaires peuvent l'emprunter pour se rendre de $a$ à $b$. En revanche, au retour de $b$ vers $a$, ils ne peuvent pas monter à bord, pour des raisons de carburant, de chargement de marchandises, etc. Lorsqu'un vaisseau est hors service, il reste en attente sur l'astre qui le gère.

Actuellement, tous les vaisseaux sont hors service. Le calendrier de leurs changements d'état futurs est fixé. Chaque changement est de l'un des types suivants :

• Mettre en service le vaisseau actuellement hors service de l'astre $a$, à destination de l'astre $b$. Cela ne se produit que si les passagers ordinaires ne peuvent pas aller de $b$ à $a$ en empruntant successivement des vaisseaux.
• Mettre hors service le vaisseau actuellement en service de l'astre $a$.

Deux personnes qui prévoient de voyager dans cette galaxie ont préparé plusieurs questions de la forme suivante afin d'organiser leurs rendez-vous :

• À un instant donné du calendrier, si l'une se trouve sur l'astre $a$ et l'autre sur l'astre $b$, peuvent-elles se rejoindre en utilisant les vaisseaux comme passagers ordinaires ? Si oui, sur quel astre doivent-elles se rejoindre pour minimiser le nombre d'utilisations de vaisseaux ? Autrement dit, existe-t-il un astre $c$ accessible aussi bien depuis $a$ que depuis $b$ en empruntant successivement des vaisseaux comme passagers ordinaires ? Si oui, quel astre $c$ minimise la somme du nombre d'utilisations nécessaires pour aller de $a$ à $c$ et du nombre d'utilisations nécessaires pour aller de $b$ à $c$ ?

Vous êtes un excellent programmeur, et l'on vous demande de répondre à toutes leurs questions.

Énoncé

Écrivez un programme qui répond aux questions, étant donnés le calendrier des changements d'état des vaisseaux et les questions, dans l'ordre chronologique.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient deux entiers $N$ et $Q$ séparés par une espace : $N$ est le nombre d'astres et $Q$ est la somme du nombre de changements d'état et du nombre de questions.
• Les $Q$ lignes suivantes décrivent les changements d'état et les questions dans l'ordre chronologique. La $i$-ième de ces lignes ($1 \le i \le Q$) contient deux ou trois entiers séparés par des espaces. Si l'on note $T_i$ le premier entier, l'un des cas suivants s'applique.

(i) $T_i = 1$

La ligne contient les entiers $T_i$, $A_i$, $B_i$ et décrit le changement suivant : mettre en service le vaisseau de l'astre $A_i$ à destination de l'astre $B_i$.

Il est garanti que $1 \le A_i \le N$, $1 \le B_i \le N$ et $A_i \ne B_i$, que le vaisseau de l'astre $A_i$ est actuellement hors service et qu'à cet instant, les passagers ordinaires ne peuvent pas aller de $B_i$ à $A_i$ en empruntant successivement des vaisseaux.

(ii) $T_i = 2$

La ligne contient les entiers $T_i$, $A_i$ et décrit le changement suivant : mettre hors service le vaisseau de l'astre $A_i$.

Il est garanti que $1 \le A_i \le N$ et que le vaisseau de l'astre $A_i$ est actuellement en service.

(iii) $T_i = 3$

La ligne contient les entiers $T_i$, $A_i$, $B_i$ et décrit la question suivante : si, à cet instant, une personne se trouve sur l'astre $A_i$ et l'autre sur l'astre $B_i$, peuvent-elles se rejoindre en empruntant les vaisseaux comme passagers ordinaires ? Si oui, quel astre de rendez-vous minimise le nombre d'utilisations de vaisseaux ?

Il est garanti que $1 \le A_i \le N$, $1 \le B_i \le N$ et $A_i \ne B_i$.

Sortie

Pour chaque question, affichez sur la sortie standard, dans l'ordre et sur une ligne distincte :

• si les deux personnes peuvent se rejoindre, le numéro de l'astre de rendez-vous qui minimise le nombre d'utilisations de vaisseaux ;
• sinon, l'entier $-1$.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [10 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [30 points]

• $T_i \ne 2$ pour tout $1 \le i \le Q$.

Sous-tâche 3 [60 points]

Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

-1
4

Remarque

Dans cet exemple, les changements d'état et les questions sont les suivants, dans l'ordre :

• Le vaisseau de l'astre $2$ est mis en service à destination de l'astre $4$.
• À cet instant, deux personnes sur les astres $2$ et $6$ ne peuvent pas se rejoindre ; on affiche donc $-1$.
• Le vaisseau de l'astre $4$ est mis en service à destination de l'astre $3$.
• Le vaisseau de l'astre $6$ est mis en service à destination de l'astre $4$.
• À cet instant, deux personnes sur les astres $2$ et $6$ peuvent se rejoindre sur l'astre $3$ ou sur l'astre $4$. Pour minimiser le nombre d'utilisations de vaisseaux, elles doivent se rejoindre sur l'astre $4$ ; on affiche donc $4$.

Entrée 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

Sortie 2

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