공연장 좌석 그룹 관리

문제

한 공연장에 1번부터 N번까지 번호가 붙은 좌석이 있다. 처음에는 좌석마다 자기 혼자만 있는 단체 그룹에 속해 있다. 관리 프로그램은 다음 네 종류의 명령을 순서대로 Q개 처리한다. 명령 1 a b는 좌석 a가 속한 그룹과 좌석 b가 속한 그룹을 하나로 합친다. 두 좌석이 이미 같은 그룹이면 아무 일도 일어나지 않는다. 명령 2 a는 좌석 a를 현재 속한 그룹에서 빼내어 a 혼자만 있는 새 그룹으로 만든다. 좌석 a가 이미 혼자라면 아무 일도 일어나지 않는다. 이때 원래 그룹의 나머지 좌석들은 서로 같은 그룹으로 계속 남는다. 명령 3 a는 좌석 a가 속한 그룹의 좌석 수를 출력한다. 명령 4는 지금 존재하는 그룹의 수를 출력한다. 출력이 필요한 명령(3과 4)에 대해서만 답을 한 줄에 하나씩 입력 순서대로 출력하는 프로그램을 작성하라. 입력에는 명령 3 또는 명령 4가 적어도 하나 있다. 명령 1에서 a와 b가 같은 번호일 수도 있다.

입력

첫 줄에 N과 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 200000) 다음 Q개의 줄에 명령이 하나씩 주어진다. 명령은 "1 a b", "2 a", "3 a", "4" 중 하나이며 1 ≤ a, b ≤ N이다. 입력 전체의 길이는 400KB 이하이다.

출력

명령 3과 4마다 결과를 한 줄에 하나씩 출력한다.

5 8
1 1 2
1 2 3
3 1
2 2
3 3
3 2
4
1 2 2

3
2
1
4

3 5
2 1
1 1 3
2 3
4
3 1

3
1

출처: Devin.KR 자체 제작