#214839. 「yrOI R1」冬日永恒

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

• 建立一个新点 ，对 连边 。你需要时刻保证目前存在的点的个数 。
• 如果当前的图中存在环，你可以选择一个简单环并删除它上面所有的边，重复此流程直到没有环存在。
• 删除所有度数为 的点。

现在，给你两棵树 ，，你需要判断， 能否进行若干次操作得到森林集合 ， 只包含一棵树 ，并且 与 同构。

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

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

接下来输入 组数据：

第一行输入三个数 ，代表 树的大小和 。

接下来 行每行输入一条边 ，代表树 的一条边。

接下来 行每行输入一条边 ，代表树 的一条边。

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

第一行输出一个字符串 或者 ，代表是否可以让 通过操作与 同构。

如果你输出了 ，接下来一行你需要输出一个数 ，代表你构造方案的操作次数。

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

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

第一行输出 个数，代表你选择的点，接下来在 个点后面输出一个数 ，代表你新建的点。注意： 必须曾经被删除过或者从未出现于 。你需要保证 。

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

最后你需要输出一行 ，代表操作后的 树中 对应 树的 。

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

样例输入 1

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

样例输出 1

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

本题开启子任务测试，但是不绑点。记 。

• Subtask 1（20 pts）：。
• Subtask 2（40 pts）：。
• Subtask 3（40 pts）：。

每个子任务有 个测试点，每个测试点等分获得该子任务的分数。记 为 的最大可能值，二十个测试点的 。

第 个子任务的第 个测试点编号为 。

对于每个 subtask 的第 个测试点：，，，。

对于 的数据：，，，。

， 见下表：

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