C++ DSU

DSU(Disjoint Set Union)는 서로 겹치지 않는 집합들을 관리하는 자료구조이다.

초기에 $1$부터 $N$까지 번호가 붙은 $N$개의 원소가 있다. 각 원소는 서로 다른 집합에 속해 있다.

$Q$개의 쿼리를 순서대로 처리하라.

쿼리는 다음 중 하나이다.

• merge a b: 원소 $a$가 속한 집합과 원소 $b$가 속한 집합을 합친다. 이미 같은 집합에 속해 있다면 아무 일도 일어나지 않는다. $(1 \leq a,b \leq N)$
• same a b: 원소 $a$와 원소 $b$가 같은 집합에 속해 있다면 1, 아니라면 0을 출력한다. $(1 \leq a,b \leq N)$
• size a: 원소 $a$가 속한 집합의 크기를 출력한다. $(1 \leq a \leq N)$

첫 번째 줄에 원소의 개수 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 10^6)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

same, size 쿼리가 주어질 때마다 쿼리의 결과를 한 줄에 하나씩 출력한다.