소비에트 Union-Find

Evan Streb의 이미지, Vezanmatics. 허가를 받아 사용함.

Ingfríður는 역사 수업에서 지루해하며 앉아 있었다. 선생님은 소련과 냉전에 관해 이야기하고 있었다. 하지만 그녀는 프로그래밍 대회와 자신이 풀고 싶은 문제를 생각하느라 너무 바빴다. 그래서 진행 중인 수업에는 전혀 집중하지 않았다.

그런데 수업이 끝날 무렵, 선생님은 이 시대와 관련된 자유로운 창작 과제를 해야 한다고 말했다. 그녀는 이와 관련해 무엇을 할 수 있을지 오랫동안 깊이 생각했지만, 여전히 경쟁 프로그래밍 생각에서 벗어나지 못했다. 마침내 그녀에게 생각이 떠올랐다. Soviet Union은 분명 Union-Find 자료 구조와 관련이 있을 것이다. Soviet Union은 당연히 선생님이 이야기하던 소비에트 사회주의 공화국 연방의 영어 명칭이다. 따라서 그녀는 그것과 관련된 과제를 할 수 있다. 하지만 이제 제출 기한이 바로 코앞인데, 그녀는 이 과제를 하는 것을 잊고 있었다. 그녀를 구하기 위해 소비에트 Union-Find를 구현해 줄 수 있는가?

소비에트 Union-Find는 여러 연산을 지원해야 한다. 처음에 세계의 영토를 $n$개의 구역으로 나누고 그 구역들에 $1, 2, \dots, n$의 번호를 매긴다. 처음에는 각 구역이 각자 하나의 독립 국가이며, 그 구역이 해당 국가의 지배자이다. 그러나 이후 입력으로 여러 연산이 주어질 수 있다. 첫 번째는 a x y이며, 이는 구역 $x$를 포함하는 국가가 구역 $y$를 포함하는 국가를 점령한다는 뜻이다. 새롭게 합쳐진 국가의 지배자는 합병 전에 구역 $x$를 지배하던 구역이 된다. 다음 연산은 b x이며, 이는 구역 $x$를 포함하는 국가가 발칸화된다는 뜻이다. 이는 그 국가의 모든 구역이 분리되어 처음처럼 다시 각각 하나의 국가가 된다는 뜻이다. 마지막으로 c x 연산은 현재 구역 번호 $x$를 누가 지배하는지 묻는다.

채점

그룹 | 점수 | 제한

1 | 25 | $n = 2, q \leq 100$

2 | 25 | $n, q \leq 1\,000$

3 | 25 | 입력에 b 연산이 없다.

4 | 25 | 추가 제한 없음.

입력의 첫 줄에는 두 양의 정수 $n, q$가 주어진다. 여기서 $n$는 세계의 영토를 나눈 구역의 수이고, $q$는 연산의 수이다. 이어서 각각 하나의 연산을 담은 $q$개의 줄이 주어진다. 각 줄의 첫 문자는 위에서 설명한 대로 항상 a, b 또는 c이며, 이 문자가 연산의 종류를 나타낸다.

문자가 a라면, 그 뒤에 $1 \leq x, y \leq n$를 만족하는 두 양의 정수 $x$와 $y$가 주어진다. $x$와 $y$가 이미 같은 국가의 일부라면 이 연산은 아무것도 하지 않는다. 그렇지 않으면 위에서 설명한 대로 $x$와 $y$에 합병 연산을 수행한다.

문자가 b라면, 그 뒤에 $1 \leq x \leq n$를 만족하는 하나의 양의 정수 $x$가 주어진다. 그러면 위에서 설명한 대로 $x$에 발칸화 연산을 수행한다.

마지막으로 문자가 c라면, 그 뒤에 $1 \leq x \leq n$을 만족하는 하나의 양의 정수 $x$가 주어진다. 항상 $n, q \leq 100\,000$가 성립한다.

입력의 각 c 연산에 대해, 위에서 설명한 대로 그 연산에서 주어진 구역을 지배하는 구역의 번호를 출력한다. 각 수를 별도의 줄에, 연산이 입력으로 주어진 순서와 같은 순서로 출력한다.