背景

题目描述

我们对一个森林集合定义一次操作为，选择 $k$ 个互不相同的点 $u_{1 \sim k}$（如果不能选择则不能操作），然后依次进行以下流程：

• 建立一个新点 $n'$，对 $i \in [1, k]$ 连边 $(n',u_i)$。你需要时刻保证目前存在的点的个数 $\le \max(n_1,n_2)+5$。
• 如果当前的图中存在环，你可以选择一个简单环并删除它上面所有的边，重复此流程直到没有环存在。
• 删除所有度数为 $0$ 的点。

现在，给你两棵树 $S,T$，$n_1=|S|,n_2=|T|$，你需要判断，$G=\{S\}$ 能否进行若干次操作得到森林集合 $G'$，$G'$ 只包含一棵树 $S'$，并且 $S'$ 与 $T$ 同构。

由于出题人非常善良，你可以进行 $m$ 次操作，$m$ 见数据范围。

输入格式

第一行输入两个数 $c,t$，代表测试点编号和数据组数。特别地，样例中 $c=0$。

接下来输入 $t$ 组数据：

第一行输入三个数 $n_1,n_2,k$，代表 $S,T$ 树的大小和 $k$。

接下来 $n_1-1$ 行每行输入一条边 $(u_i,v_i)$，代表树 $S$ 的一条边。

接下来 $n_2-1$ 行每行输入一条边 $(x_i,y_i)$，代表树 $T$ 的一条边。

输出格式

你需要输出 $t$ 组数据的答案：

第一行输出一个字符串 $\texttt{Yes}$ 或者 $\texttt{No}$，代表是否可以让 $S$ 通过操作与 $T$ 同构。

如果你输出了 $\texttt{Yes}$，接下来一行你需要输出一个数 $r$，代表你构造方案的操作次数。

你需要保证你的操作次数小于等于 $m$ 次，如果你的操作次数超过了 $m$，将会被判定为 Wrong Answer。

接下来你需要输出你进行的 $r$ 次操作：

第一行输出 $k$ 个数，代表你选择的点，接下来在 $k$ 个点后面输出一个数 $n'$，代表你新建的点。注意：$n'$ 必须曾经被删除过或者从未出现于 $G'$。你需要保证 $n' \le \max(n_1,n_2) + 5$。

接下来输出一个整数 $l$，代表你删除的简单环个数，接下来 $l$ 行每行描述一个删除的简单环，第 $i$ 行首先输出环的长度 $h_i$，接下来输出一个顶点序列 $u_{1 \sim h_i}$ 代表你删除的环，请注意，必须按任意一种环上的方向依次输出 $u_{1 \sim h_i}$。

最后你需要输出一行 $p_x$，代表操作后的 $S'$ 树中 $p_x$ 对应 $T$ 树的 $x$。

本题开启 Special Judge，如果有多种方案，输出任意一种即可。如果你的方案不合法，将会被判定为 WA/UKE。

0 3
4 3 2
1 2
2 3
3 4
2 1
2 3
4 4 3
1 2
2 3
3 4
1 2
1 3
1 4
4 4 4
1 2
1 3
1 4
1 2
2 3
3 4

Yes
1
3 4 5
1
3 3 4 5
1 2 3
Yes
1
2 3 4 5
1
3 5 3 4
2 1 3 5
No

提示

本题开启子任务测试，但是不绑点。记 $N = \max(n_1,n_2)$。

• Subtask 1（20 pts）：$k=2$。
• Subtask 2（40 pts）：$k=3$。
• Subtask 3（40 pts）：$k=4$。

每个子任务有 $20$ 个测试点，每个测试点等分获得该子任务的分数。记 $N_{\max}$ 为 $N$ 的最大可能值，二十个测试点的 $\{N_{\max}\}=\{3,5,8,20,50,100,300,500,700,1000,1000,1000,1000,2 \times 10^4,4 \times 10^4,6\times 10^4,8 \times 10^4,10^5,10^5,10^5\}$。

第 $i$ 个子任务的第 $j$ 个测试点编号为 $20(i-1)+j$。

对于每个 subtask 的第 $1 \sim 13$ 个测试点：$1 \le T \le 10^3$，$2 \le n_1,n_2 \le 10^3$，$k \in \{2,3,4\}$，$\sum N^2 \le 10^8$。

对于 $100\%$ 的数据：$1 \le T \le 10^3$，$2 \le n_1,n_2 \le 10^5$，$k \in \{2,3,4\}$，$\sum N \le 5 \times 10^5$。

$m=m_0+10$，$m_0$ 见下表：

「我觉得...只有在什么结束的时候，才能开始达到永恒」‌