문제 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