시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.75 초 (추가 시간 없음) 8 MB (추가 메모리 없음)191797348.993%

문제

메모리 제한에 주의하세요

엄청나게 머나 먼 미래, 새로운 삶의 터전을 찾아 떠난 인류는 고대에 엄청나게 큰 뱀이 살았다는 빌라봉 행성을 발견한다. 빌라봉 행성은 대부분 바다여서 모든 땅은 섬이었지만, 고도로 발전된 기술 덕분에 인류는 빌라봉 행성에 쉽게 정착할 수 있었다. 하지만 잦은 다툼 때문에 하나로 합치지 못하고 서로 다른 나라를 세워 살게 되었다. 

각 나라는 한 개 이상의 섬을 지배하고 있고, 어떤 나라에도 속하지 않은 섬은 없으며, 하나의 섬은 두 개 이상의 나라가 지배할 수 없다.

섬은 여러 개의 도시와 서로 다른 도시를 잇는 도로로 이루어져 있다. 같은 섬에서 임의의 두 도시 사이의 경로는 항상 유일하다.

기술이 고도로 발전했기 때문에 섬 사이를 잇는 도로를 만들어, 서로 떨어져 있던 섬들을 하나로 합칠 수 있다. 빌라봉 행성의 섬나라들은 주변국과 사이가 좋지 않기 때문에, 서로 다른 두 나라의 섬을 잇는 도로는 만들 수 없다. 또한 이미 경로가 존재하는 두 도시를 잇는 도로를 만드는 것은 비효율적이기 때문에, 같은 섬의 두 도시를 잇는 도로는 만들지 않는다.

때때로 빌라봉 행성의 특정 지역에는 빌라봉온난화 현상으로 해수면이 상승해 도로가 파괴될 수 있다. 이 경우 하나의 섬이 여러 개의 섬으로 나뉘고, 나뉜 섬들은 기존 섬을 지배하던 나라가 지배한다.

빌라봉 행성의 저명한 지리학자 기웅이는 특정 시점에 각 나라가 몇 개의 섬을 지배하고 있는지 궁금해졌다. 기웅이에게는 어려운 문제이지만, 똑똑한 여러분은 해낼 수 있을 거라 믿는다!

입력

첫째 줄에 나라의 개수 $N$이 주어진다. 각 나라는 $1$이상 $N$이하의 정수로 나타낸다. ($1 \leq N \leq min(193^ 2, \sum V)$, $\sum V \leq 1\ 000\ 000$)

둘째 줄부터는 $N$개의 나라에 대한 정보가 주어진다. 각 나라에 해당하는 첫째 줄에는 도시의 개수 $V_i$와 초기 도로의 개수 $E_i$가 주어지고, 각 나라의 도시는 $\sum^{i-1} V + 1$부터 $\sum^i V$ 까지 정수로 나타낸다. ($0 \leq E_i < V_i$)

다음 $E_i$개 줄에는 같은 나라의 서로 다른 도시를 잇는 도로의 정보가 주어진다. 같은 섬에서 임의의 두 도시 사이의 경로는 항상 유일하다.

다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \leq Q \leq 100\ 000$)

다음 $Q$개 줄에는 쿼리가 주어진다. 쿼리는 다음 $3$가지 형태 중 하나다.

  • $1$ $k$ : $k$번 나라가 지배하는 섬의 수를 출력한다. 최소 한번 이상 주어진다. ($1 \leq k \leq N$)
  • $2$ $u$ $v$ : 빌라봉온난화 현상으로 두 도시 $u$와 $v$를 잇는 도로가 파괴된다. 이미 도로가 존재하는 경우에만 주어진다.
  • $3$ $u$ $v$ : 고도의 기술력을 이용해 두 도시 $u$와 $v$를 잇는 도로를 만든다. 아직 도로가 없는 경우에만 주어진다.

출력

$1$번 쿼리가 주어질 때마다, $k$번 나라가 지배하는 섬의 수를 출력한다.

예제 입력 1

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

예제 출력 1

2
1

예제 입력 2

4
5 3
1 2
1 3
5 4
3 0
5 4
10 9
10 11
10 12
10 13
6 5
15 16
16 17
17 18
17 19
14 19
13
1 2
2 16 17
2 9 10
1 4
2 10 12
3 9 12
1 3
3 1 5
1 1
3 14 15
2 1 2
1 1
1 4

예제 출력 2

3
2
2
1
2
1

노트

$193$은 문제 출제 시점, UN에 가입한 정회원국의 수이다.

제출할 수 있는 언어

C++17, C11, C99, C++11, C++14, C++20