Description

在大学里，Caroline 开始学习仙人掌图。她的老师为了检验学生是否真正理解仙人掌的定义，布置了以下家庭作业问题：

给定两个具有相同顶点数和边数的仙人掌图。你的任务是判断是否可以通过最多 $15\,000$ 次以下两步操作，将第一个仙人掌图转换为第二个仙人掌图：

1. 从第一个仙人掌图中选择任意一条边并删除（注意：此操作后，图不一定是仙人掌图）；
2. 向第一个图中添加一条原本不存在的边，使得图重新成为仙人掌图。

注意：该操作包含两个步骤，因此必须执行这两个动作。

题目保证，如果可以将第一个仙人掌图转换为第二个仙人掌图，则最多使用 $15\,000$ 次操作即可完成。

老师承诺，任何解决此问题的学生将无需考试直接获得满分。由于给定的仙人掌图规模较大，Caroline 无法在短时间内独立解决该问题，因此她请你帮忙编写一个程序来解决该问题。

仙人掌图是一种连通无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是允许存在某些环的树的推广。仙人掌图中不允许存在重边（一对顶点之间的多条边）或自环（连接顶点自身的边）。

如果对于任意顶点对 $v$ 和 $u$（$1 \leq v < u \leq n$），两个仙人掌图中要么同时存在边 $(v, u)$，要么同时不存在，则称这两个仙人掌图相同。

Input Format

第一行包含两个整数 $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$ 行描述第二个仙人掌图。

Output Format

如果无法将第一个仙人掌图转换为第二个仙人掌图，则输出一行 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$ 表示被添加边的顶点。

5 5
1 2
3 1
2 4
3 4
4 5
1 2
3 2
3 1
4 1
3 5

YES
3
3 4 2 3
5 4 3 5
2 4 1 4

5 6
1 2
2 3
1 3
4 3
3 5
5 4
1 2
2 4
4 1
4 3
3 5
4 5

NO

Hint

样例 1 解释

样例 2 解释

翻译由 DeepSeek V3 完成