8598: Equivalence in Connectivity

当一个图中存在uu到vv的路径时，且仅当另一个图中存在uu到vv的路径，且所有1\le u



给定kk图G_1G

1



, G_2G

2



, \ cdots⋯,G_kG

k



对于规模nn，对于每个i=2i= 2,33， \cdots, kk，存在p_i

我




我



可以从G_{p_i}G

p

我







通过添加或删除一条边。将它们分组，使两个图在连通上等价时，且仅当它们在连通上等价时，它们在同一组中。

有多个测试用例。第一行输入包含一个整数TT(1\le T\le 10^51≤T≤10)

5

)，测试用例的数量。对于每个测试用例:

第一行包含三个整数kk, nn和mm (1\ lek1≤k, n\le10^5n≤10)

5

, 0 \ \勒勒米\ min(10 ^ 5 \压裂{n (n - 1)} 2) 0≤m≤分钟(10

5

，

2

n (n−1)



)) -图的数量，每个图的顶点数量，以及G_1G的边的数量

1



．



下面每条mm线包含两个整数uu和vv (1\le u

1



连接uu和vv。保证G_1G中不存在多条边

1



．



后面k-1k−1行的第ii行包含一个整数p_{i+1}p

我+ 1



，字符串t_{i+1}t

我+ 1



和两个整数x_{i+1}x

我+ 1



和y_ {i + 1} y

我+ 1



le p_ (1 \ {i + 1} \ le i1≤p

我+ 1



≤i, 1\le x_{i+1}

我+ 1



< y

我+ 1



≤n)。t_it

我



是“添加”和“删除”的一种



如果t_ {i + 1} = t识别

我+ 1



= "添加",G_ {i + 1} G

我+ 1



由G_{p_{i+1}}G

p

我+ 1







通过添加一条连接x_{i+1}x的边

我+ 1



和y_ {i + 1} y

我+ 1



． 保证G_{p_{i+1}}G中不存在这条边

p

我+ 1







．



如果t_ {i + 1} = t识别

我+ 1



= "删除",G_ {i + 1} G

我+ 1



由G_{p_{i+1}}G

p

我+ 1







通过移除连接x_{i+1}x的边

我+ 1



和y_ {i + 1} y

我+ 1



。保证G_{p_{i+1}}G上存在边

p

我+ 1







．



保证所有测试用例的nn、mm和kk之和不超过10^510

5

．

对于每个测试用例:



输出一个整数rr—第一行的组数。



对于每个组，输出一个整数kk和kk -组的大小和一行中的图形数量。



您可以以任何顺序输出组和图形。