33628번 - Connect the GSHS 서브태스크

문제

대한민국의 명소 경기과학고등학교에는 $N$개의 건물이 있으며, 각 건물은 1ドル$부터 $N$까지 번호가 매겨져 있다. 원래는 건물들 사이를 연결하는 도로가 존재했지만, 서울과학고등학교 학생들이 "Split the GSHS!" 를 외치며 모든 도로를 제거해 버렸다.

이를 보고 분노한 재우는 우현이를 시켜 도로를 다시 건설하려 한다.

도로는 서로 다른 두 건물을 양방향으로 연결한다. 한 건물에서 도로 몇 개를 통해 다른 건물까지 갈 수 있다면, 두 건물이 연결되어 있다고 한다. 이때 두 건물 사이의 거리는 두 건물 사이를 이동하기 위해 지나야 하는 도로 수의 최솟값이다.

어떤 건물과 연결되어 있는 모든 건물 중 번호가 가장 작은 건물을 그 건물의 '관리 건물'이라고 하자. 정의에 따라, 어떤 건물과 연결되어 있는 모든 건물의 관리 건물은 같게 된다.

재우는 우현이에게 $Q$번의 명령을 내린다. 명령은 다음 두 가지 유형으로 이루어진다.

• 1ドル$ $A$ $B$: 건물 $A$와 $B$ 사이에 도로를 연결한다. 도로를 연결하기 전, $A$와 $B$ 모두로 이동할 수 있는 건물이 존재하지 않음이 보장된다.
• 2ドル$ $A$ $B$: 건물 $A$와 건물 $B$가 연결되어 있다면, 두 건물 사이를 최단거리로 이동하기 위해 지나야 하는 건물 (건물 $A$와 건물 $B$를 포함) 중 건물 $A$의 관리 건물과 가장 가까운 건물의 번호를 출력한다. 만약 두 건물이 연결되어 있지 않다면 0ドル$을 출력한다.

여러분은 우현이다. 재우의 명령들을 모두 수행해라.

입력

첫 번째 줄에 경기과학고등학교의 건물의 수를 나타내는 정수 $N$과 재우가 우현이에게 내리는 명령의 개수 $Q$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $Q$개의 줄에는 쿼리의 종류를 나타내는 $T$와 두 정수 $X, Y$가 공백을 사이에 두고 주어진다. 이때,

• $A=X \oplus $last_ans
• $B=Y \oplus $last_ans

에 대해 명령 $T$ $A$ $B$를 수행하여라. last_ans는 가장 마지막으로 수행한 2번 명령에서 출력한 값이며, 만약 2번 쿼리를 이전까지 한 번도 수행하지 않았다면 0이다.($\oplus$는 배타적 논리합(xor)을 의미한다)

출력

$i$번째 줄에 $i$번째 2번 쿼리에 대한 정답을 출력한다.

제한

• 2ドル \le N \le 10^5$
• 2ドル \le Q \le 5 \times 10^5$

서브태스크

힌트