若两个大小为 $n$ 的无向图对于所有 $1 \le u < v \le n$，满足“在其中一个图中存在从 $u$ 到 $v$ 的路径”当且仅当“在另一个图中存在从 $u$ 到 $v$ 的路径”，则称这两个图在连通性上是等价的。

给定一个包含 $k$ 个图的序列 $G_1, G_2, \dots, G_k$。每个图的大小均为 $n$。在该序列中，对于每个 $i = 2, 3, \dots, k$，存在一个 $p_i < i$，使得 $G_i$ 可以通过在 $G_{p_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})$)：分别表示图的数量、每个图的顶点数以及 $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$：组数。

对于每一组，输出一行，包含一个整数 $k$ 以及 $k$ 个整数：该组的大小以及组内图的编号。

你可以以任意顺序输出组和组内的图。

样例

输入 1

2
15 11 8
6 11
1 6
6 9
6 8
1 2
1 5
9 10
2 5
1 add 3 11
1 add 2 3
3 add 5 8
4 add 5 11
3 add 7 10
1 add 6 10
3 add 3 10
1 remove 6 8
5 add 4 9
1 add 2 9
8 add 7 8
3 add 2 4
1 remove 6 9
10 remove 6 9
14 5 2
1 5
1 4
1 add 2 4
1 add 3 4
1 add 2 4
4 add 3 4
4 add 1 3
5 add 1 3
2 add 2 3
1 add 1 2
4 add 3 4
3 add 4 5
9 add 2 3
3 remove 1 5
3 remove 3 4

输出 1

7
2 10 13
5 2 3 4 5 8
3 1 7 11
1 14
2 6 12
1 9
1 15
5
3 2 4 9
6 5 6 7 8 10 12
2 1 14
2 3 11
1 13