题目描述

公元 2076 年，人类舰队远征 ZY 星，准备一举将其占领。ZY 星的舰队已经被完全摧毁。现在只需要派遣部队进入 ZY 星即可获得胜利。但是 ZY 星拥有一个力场护盾，凭战舰的火力无法击穿。于是人类舰队的总司令——hjz——计划将所有战舰的能量集中到一艘战舰上，以击穿强大的护盾。战舰之间可以通过能量链接任意传输能量，但是有以下三条限制：

• 任意的能量链接只能出现在一条由链接组成的回路里，否则会由于过载产生无法估量的后果。
• 任意两艘战舰之间必须可以直接或间接通过能量链接互相到达，否则无法正常进行能量传输。
• 对于任意两条能量链接，它们连接的两艘战舰不完全相同。同样的，不存在一条能量链接的两端是同一艘战舰。

目前人类舰队拥有 $n$ 艘战舰，通过 $m$ 条能量链接相连通。保证此时满足以上三条限制。hjz 将会给出另外一种连接方式。保证这个连接方式仍然有 $m$ 条能量链接并且满足限制。hjz 希望舰队用他给出的方式连接。为了达成这个目的，他可以进行若干操作，每个操作会删除一条能量链接并同时加入另一条能量链接，并且需要保证在每个操作结束后连接方式仍然合法。兵贵神速，战机稍纵即逝。hjz 希望在 $15000$ 次操作内达成目标。你作为 hjz 手底下的参谋，需要给出一个符合条件的方案。如果这样的方案不存在，请回答：“不可以，总司令。”

输入格式

第一行两个整数，表示 $n,m$。 后面 $m$ 行，每行两个整数 $u_i,v_i$，表示第 $i$ 条能量链接连接战舰 $u_i$ 和 $v_i$。 后面 $m$ 行，每行两个整数 $x_i,y_i$，表示 hjz 的方案中 第 $i$ 条能量链接连接战舰 $x_i$ 和 $y_i$。

输出格式

如果不存在这样的方案，输出 NO。

否则，第一行输出 YES，第二行输出一个正整数 $c$，表示操作次数。你需要保证 $c\leq 15000$。

后面 $c$ 行，每行四个正整数 $a_i,b_i,c_i,d_i$，表示在第 $i$ 个操作中断开了 $a_i,b_i$ 间的能量链接，并在 $c_i,d_i$ 间加入了一条能量链接。

样例

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
1 3
2 3
3 4
3 5
4 5
1 2
1 3
2 3
1 4
1 5
4 5

NO

数据范围

特殊性质 A：$m=n-1$。

特殊性质 B：任意回路均只包含三条能量链接。

对于所有数据，$1\leq n\leq 1000,n-1\leq m\leq \lfloor\frac{3(n-1)}{2}\rfloor,1\leq u_i,v_i,x_i,y_i\leq n$。

spj

checker.cpp

使用方法：将其编译，假设输入文件为 in.txt，输出文件为 out.txt，答案文件为 ans.txt，将这三个文件和编译出的可执行文件放在同一个文件夹下，根据系统的不同：

• Windows：假设可执行文件名叫 checker.exe，则在该文件夹的终端中输入 checker.exe in.txt out.txt ans.txt。
• Linux：假设可执行文件名叫 checker，则在该文件夹的终端中输入 ./checker in.txt out.txt ans.txt。

如果你没有答案文件，可将输出文件当作答案文件。此时 spj 只会检查你的方案的正确性，不会判断有无解。