대화방 합치기와 나가기

문제

어느 회사의 사내 메신저에는 1번부터 N번까지 번호가 붙은 N명의 사용자가 있다. 처음에는 모든 사용자가 자기 혼자만 있는 대화방에 들어 있다. 메신저 관리자는 다음 네 종류의 기록을 순서대로 Q개 남겼다. 1 a b: a가 속한 대화방과 b가 속한 대화방을 하나로 합친다. 이미 같은 방이면 아무 일도 일어나지 않는다. 2 a: 사용자 a가 현재 대화방에서 나가 자기 혼자만 있는 새 대화방을 만든다. 그 방에 a 혼자 있었더라도 새 방으로 옮긴 것으로 보며 결과는 같다. 나간 뒤에도 남은 사람들은 서로 계속 같은 방에 있다. 3 a b: a와 b가 지금 같은 대화방에 있으면 YES, 아니면 NO를 답한다. a와 b가 같은 사용자일 수도 있으며 이때는 YES이다. 4 a: a가 속한 대화방에 있는 사람 수를 답한다. 합치기와 나가기가 여러 번 섞여도, 방은 항상 그 시점에 실제로 들어 있는 사용자들로만 정의된다. 3번과 4번 기록에 대한 답을 기록 순서대로 한 줄에 하나씩 출력하라. 입력에는 3번 또는 4번 기록이 적어도 하나 있다.

입력

첫째 줄에 N과 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 이어지는 Q개의 줄에 각각 기록이 주어진다. 기록은 1 a b, 2 a, 3 a b, 4 a 중 하나이며 1 ≤ a, b ≤ N인 정수이다. 3번 또는 4번 기록이 적어도 하나 존재한다.

출력

3번과 4번 기록에 대한 답을 순서대로 한 줄에 하나씩 출력한다. 3번 기록의 답은 YES 또는 NO이고, 4번 기록의 답은 정수이다.

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

3
NO
2
YES
1

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

1
YES
NO

출처: Devin.KR 자체 제작