在大学里，Caroline 开始学习仙人掌图（cactus graphs）。她的老师为了检查学生是否真正理解了仙人掌的定义，布置了以下作业：

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

• 从第一个仙人掌中选择一条任意边并将其删除（注意，在此操作后，该图不一定仍是仙人掌）；
• 在第一个图中添加一条任意不存在的边，使得该图变回仙人掌。

注意，该操作包含上述两个步骤，因此你必须同时执行这两步。

题目保证，如果可以将第一个仙人掌变换为第二个，那么一定可以在 $15\,000$ 次操作内完成。

老师承诺，任何解决此问题的人都可以免试获得满分。由于给定的仙人掌规模很大，且 Caroline 无法在短时间内独立解决，她请求你编写一个程序来解决这个问题。

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

如果对于任意一对顶点 $v$ 和 $u$ ($1 \le v < u \le 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 \neq v \le n$)，表示仙人掌的边。前 $m$ 行表示第一个仙人掌，后 $m$ 行表示第二个仙人掌。

输出格式

如果无法将第一个仙人掌变换为第二个，输出一行单词 “NO”。

否则，第一行输出单词 “YES”。第二行输出一个整数 $c$ ($0 \le c \le 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

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

输出 1

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

输入 2

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

输出 2

NO