동적 숲의 최소 공통 조상

정점 하나로만 이루어진 루트 있는 트리가 N개 있다. 정점에는 1번부터 N번까지 번호가 매겨져 있고, 처음에는 모든 정점이 자기 자신만으로 이루어진 트리의 루트다.

다음 세 가지 쿼리를 주어진 순서대로 처리하는 프로그램을 작성하시오.

• 1 u v: u와 v를 잇는 간선을 하나 추가한다. 이때 v가 u의 부모가 된다. 이 쿼리를 처리하기 직전에 u는 자신이 속한 트리의 루트이고, u와 v는 서로 다른 트리에 속한다.
• 2 v: v와 v의 부모를 잇는 간선을 끊는다. v는 루트가 아니다. 간선을 끊고 나면 v가 새로운 트리의 루트가 된다.
• 3 u v: u와 v의 최소 공통 조상을 출력한다. 이 쿼리를 처리하는 시점에 u와 v는 같은 트리에 속한다. u와 v가 같을 수도 있고, 그때 답은 u다.

첫째 줄에 정점의 개수 N과 쿼리의 개수 M이 주어진다. ($2 \le N \le 100000$, $1 \le M \le 200000$)

다음 M개의 줄에 위에서 설명한 형식의 쿼리가 한 줄에 하나씩 주어진다.

3번 쿼리마다 그 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.