시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

정점 하나로 이루어진 루트 있는 트리 N개가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 

아래의 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 u v: u와 v 사이에 간선을 하나 연결한다. 이 때, v가 u의 부모가 된다. 또, u는 u가 포함되어 있는 트리의 루트이었어야 하며, u와 v는 다른 트리에 속해 있었어야 한다.
  • 2 v: v와 v의 부모를 연결하는 간선을 끝는다. v는 루트가 아니다.
  • 3 u v: u와 v의 LCA를 출력한다. u와 v는 같은 트리 안에 있다.

입력

첫째 줄에 N (2 ≤ N ≤ 100,000)과 쿼리의 개수 M (1 ≤ M ≤ 200,000)이 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

출력

각각의 3번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력

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

예제 출력

1
2
3
2

힌트

출처