Il y a $N$ arbres enracinés, chacun composé d'un seul sommet. Les sommets sont numérotés de $1$ à $N$.

Écrire un programme qui exécute les requêtes suivantes :

• 1 u v : Ajouter une arête entre u et v. v devient le parent de u. Avant l'exécution de la requête, u est la racine de l'arbre contenant u, et il est garanti que u et v appartiennent à des arbres différents.
• 2 v : Supprimer l'arête reliant v à son parent. v n'est pas la racine.
• 3 u v : Afficher le LCA de u et v. u et v sont dans le même arbre.

Entrée

La première ligne contient $N$ ($2 \le N \le 100{,}000$) et le nombre de requêtes $M$ ($1 \le M \le 200{,}000$).

Les $M$ lignes suivantes contiennent les requêtes, une par ligne.

Sortie

Afficher les résultats de chaque requête de type 3 dans l'ordre, un par ligne.

Exemples

Entrée 1

5 9
3 1 1
1 1 2
1 3 2
1 4 3
3 1 4
3 3 4
2 4
1 5 3
3 1 5

Sortie 1

1
2
3
2