P12434 [NERC2023] Cactus Transformation

在大学里，Caroline 开始学习仙人掌图。她的老师为了检验学生是否真正理解仙人掌的定义，布置了以下家庭作业问题： 给定两个具有相同顶点数和边数的仙人掌图。你的任务是判断是否可以通过最多 $15\,000$ 次以下两步操作，将第一个仙人掌图转换为第二个仙人掌图： 1. 从**第一个**仙人掌图中选择**任意一条**边并删除（注意：此操作后，图不一定是仙人掌图）； 2. 向**第一个**图中添加一条**原本不存在**的边，使得图重新成为仙人掌图。 注意：该操作包含两个步骤，因此**必须**执行这两个动作。 题目保证，如果可以将第一个仙人掌图转换为第二个仙人掌图，则最多使用 $15\,000$ 次操作即可完成。 老师承诺，任何解决此问题的学生将无需考试直接获得满分。由于给定的仙人掌图规模较大，Caroline 无法在短时间内独立解决该问题，因此她请你帮忙编写一个程序来解决该问题。 **仙人掌图**是一种连通无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是允许存在某些环的树的推广。仙人掌图中不允许存在重边（一对顶点之间的多条边）或自环（连接顶点自身的边）。 如果对于任意顶点对 $v$ 和 $u$（$1 \leq v < u \leq n$），两个仙人掌图中要么同时存在边 $(v, u)$，要么同时不存在，则称这两个仙人掌图**相同**。

第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 1000$，$n - 1 \le m \le \lfloor \frac{3(n - 1)}{2} \rfloor$）——仙人掌图的顶点数和边数。接下来的 $2 \cdot m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u \ne v \le n$）——表示仙人掌图的边。前 $m$ 行描述第一个仙人掌图，后 $m$ 行描述第二个仙人掌图。

如果无法将第一个仙人掌图转换为第二个仙人掌图，则输出一行 ``NO``。 否则，第一行输出 ``YES``。第二行输出一个整数 $c$（$0 \leq c \leq 15\,000$）——操作次数。接下来的 $c$ 行，每行包含四个整数 $w_i$（$1 \le i \le 4$，$1 \le w_i \le n$）。前两个整数 $w_1$ 和 $w_2$ 表示被删除边的顶点，后两个整数 $w_3$ 和 $w_4$ 表示被添加边的顶点。

### 样例 1 解释  ### 样例 2 解释  翻译由 DeepSeek V3 完成