Equivalence in Connectivity

Two undirected graphs of size $n$ are equivalent in connectivity if, for all $1\le u<v\le n$, there is a path from $u$ to $v$ in one graph if and only if there is a path from $u$ to $v$ in the other graph.

You are given a sequence of $k$ graphs $G_1, G_2, \ldots, G_k$. Each graph has size $n$. For each $i=2,3,\ldots,k$, there exists $p_i<i$ such that $G_i$ can be obtained from $G_{p_i}$ by adding or removing one edge. Divide the given graphs into groups so that two graphs are in the same group if and only if they are equivalent in connectivity.

There are multiple test cases. The first line of input contains an integer $T$ ($1\le T\le 10^5$), the number of test cases. For each test case:

The first line contains three integers $k$, $n$, and $m$ ($1 \le k, n \le 10^5$, $0 \le m \le \min(10^5, \frac{n(n-1)}{2})$): the number of graphs, the number of vertices in each graph, and the number of edges in $G_1$.

Each of the following $m$ lines contains two integers $u$ and $v$ ($1\le u<v\le n$), denoting an edge of $G_1$ connecting $u$ and $v$. It is guaranteed that $G_1$ has no multiple edges.

The $i$-th of the following $k-1$ lines contains an integer $p_{i+1}$, a string $t_{i+1}$, and two integers $x_{i+1}$ and $y_{i+1}$ ($1\le p_{i+1}\le i$, $1\le x_{i+1}<y_{i+1}\le n$). Each string $t_{i+1}$ is either add or remove.

If $t_{i+1}$ is add, then $G_{i+1}$ is obtained from $G_{p_{i+1}}$ by adding an edge connecting $x_{i+1}$ and $y_{i+1}$. It is guaranteed that this edge does not exist in $G_{p_{i+1}}$.

If $t_{i+1}$ is remove, then $G_{i+1}$ is obtained from $G_{p_{i+1}}$ by removing an edge connecting $x_{i+1}$ and $y_{i+1}$. It is guaranteed that this edge exists in $G_{p_{i+1}}$.

It is guaranteed that, over all test cases, the sum of $n$, the sum of $m$, and the sum of $k$ are each at most $10^5$.

For each test case, output the following.

On the first line, output an integer $r$, the number of groups.

For each group, output one line containing the group size and the numbers of the graphs in the group. That is, output an integer $s$ followed by $s$ integers. The groups and the graphs within each group may be output in any order.