빌라봉 행성의 섬나라

메모리 제한에 주의하세요

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

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

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

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

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

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

첫째 줄에 나라의 개수 $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$번 나라가 지배하는 섬의 수를 출력한다.

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