연결성 동치

크기가 $n$인 두 무방향 그래프가 연결성에서 동치라는 것은 모든 $1\le u<v\le n$에 대하여 한 그래프에서 $u$와 $v$ 사이에 경로가 존재할 때, 그리고 그때에만 다른 그래프에서도 $u$와 $v$ 사이에 경로가 존재한다는 뜻이다.

$k$개의 그래프 $G_1, G_2, \ldots, G_k$가 주어진다. 각 그래프의 크기는 $n$이다. 이 수열에서 각 $i=2,3,\ldots,k$에 대하여 $G_i$가 $G_{p_i}$에서 간선 하나를 추가하거나 제거하여 얻어지는 $p_i<i$가 존재한다. 주어진 그래프를 그룹으로 나누어, 두 그래프가 연결성에서 동치일 때, 그리고 그때에만 같은 그룹에 속하게 하라.

여러 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다 ($1\le T\le 10^5$). 각 테스트 케이스는 다음과 같다.

첫 줄에는 세 정수 $k$, $n$, $m$이 주어진다 ($1 \le k, n \le 10^5$, $0 \le m \le \min(10^5, \frac{n(n-1)}{2})$). $k$는 그래프의 수, $n$은 각 그래프의 정점 수, $m$은 $G_1$의 간선 수이다.

다음 $m$개 줄 각각에는 두 정수 $u$, $v$가 주어진다 ($1\le u<v\le n$). 이는 $G_1$에서 $u$와 $v$를 잇는 간선을 뜻한다. $G_1$에는 중복 간선이 없음이 보장된다.

다음 $k-1$개 줄 중 $i$번째 줄에는 정수 $p_{i+1}$, 문자열 $t_{i+1}$, 두 정수 $x_{i+1}$, $y_{i+1}$이 주어진다 ($1\le p_{i+1}\le i$, $1\le x_{i+1}<y_{i+1}\le n$). $t_{i+1}$은 add 또는 remove이다.

$t_{i+1}$이 add이면 $G_{i+1}$은 $G_{p_{i+1}}$에 $x_{i+1}$과 $y_{i+1}$을 잇는 간선을 추가하여 얻어진다. 이 간선은 $G_{p_{i+1}}$에 존재하지 않음이 보장된다.

$t_{i+1}$이 remove이면 $G_{i+1}$은 $G_{p_{i+1}}$에서 $x_{i+1}$과 $y_{i+1}$을 잇는 간선을 제거하여 얻어진다. 이 간선은 $G_{p_{i+1}}$에 존재함이 보장된다.

모든 테스트 케이스에서 $n$의 합, $m$의 합, $k$의 합은 각각 $10^5$을 넘지 않는다.

각 테스트 케이스마다 다음을 출력한다.

첫 줄에 그룹의 수 $r$을 출력한다.

각 그룹마다 한 줄에 그룹의 크기와 그룹에 속한 그래프의 번호를 출력한다. 즉, 그룹의 크기를 나타내는 정수 $s$와 이어서 $s$개의 정수를 공백으로 구분해 출력한다. 그룹의 순서와 각 그룹 안에서 그래프의 순서는 임의로 정해도 된다.