SOJ ONLINE JUDGE

문제 109

간선 추가와 삭제

내 상태
미제출
난이도
109번 문제 난이도 보기
Diamond V
출제자
rlatjwls7882
시간 제한
1000 ms
메모리 제한
1024 MB
109번 문제 태그 보기
구현

정점이 $N$개인 무방향 그래프가 있다. 정점 번호는 $0$부터 $N-1$까지이며, 처음에는 간선이 없다. 다음 $Q$개의 연산을 순서대로 처리해 보자.

  • $0\ u\ v$: $u$와 $v$를 잇는 간선을 하나 추가한다.
  • $1\ u\ v$: $u$와 $v$를 잇는 간선을 하나 삭제한다.
  • $2\ u\ v$: 두 정점이 연결되어 있는지 판별한다.
  • $3\ u$: $u$가 속한 연결 요소의 정점 수를 구한다.
  • $4$: 연결 요소의 개수를 구한다.

자기 루프와 중복 간선이 허용된다. 간선을 삭제할 때는 해당 간선 하나만 삭제하며, 양 끝점의 순서는 구분하지 않는다. 정점은 자기 자신과 연결되어 있다.

입력

첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 본문에서 설명한 형식의 연산이 주어진다. 각 연산의 정수는 공백으로 구분되어 주어진다. $(0 \le u, v < N)$

간선을 삭제하는 연산에서는 해당 간선이 하나 이상 존재함이 보장된다.

출력

$2$번 연산에서는 두 정점이 연결되어 있다면 $1$을, 그렇지 않다면 $0$을 출력한다.

$3$번 연산에서는 구한 연결 요소의 정점 수를 출력한다. $4$번 연산에서는 구한 연결 요소 수를 출력한다.

출력이 필요한 연산이 주어진 순서대로 답을 한 줄에 하나씩 출력한다.

예제 입력 1

4 15
4
0 0 1
0 1 0
1 0 1
2 0 1
3 0
4
1 1 0
2 0 1
0 2 2
3 2
0 1 2
0 2 3
3 3
4

예제 출력 1

4
1
2
3
0
1
3
2

제출

편집기에서 나가려면 Esc를 누른 뒤 Tab 또는 Shift와 Tab을 누르세요.