동적 숲의 최소 공통 조상

시간 제한2초메모리 제한512 MB

요약

루트가 있는 트리 숲에서 링크, 컷, 최소 공통 조상 질의를 처리하며 각 LCA를 출력한다.

난이도: 어려움10점 중 9점
유형: 트리, 연결 리스트, 그래프, DFS
정답자: 아직 제출이 없습니다

문제

정점 하나로만 이루어진 루트 있는 트리가 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번 쿼리마다 그 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제6

예제 1

입력

예상 출력

예제 2
입력
```
2 1
3 1 1
```
예상 출력
```
1
```

예제 3

입력

예상 출력

예제 4

입력

예상 출력

예제 5

입력

예상 출력

예제 6

입력

예상 출력