25723번 - Equivalence in Connectivity 스페셜 저지다국어

Two undirected graphs of size $n$ are equivalent in connectivity when 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 for all $1\le u<v\le n$.

Given is a sequence of $k$ graphs $G_1, G_2, \ldots, G_k$. Each graph is of size $n$. In this sequence, 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 an edge. Divide the given graphs into groups: two graphs must be 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 \left( 10^5, \frac{n(n - 1)}{2} \right)$): 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 there are no multiple edges in $G_1$.

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 the sum of $n$, the sum of $m$, and the sum of $k$ in all test cases do not exceed $10^5$.

For each test case:

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

For each group, output a single line which contains an integer $k$ followed by $k$ integers: the size of the group and the numbers of graphs in the group.

You can output the groups and the graphs in any order.