题目描述

给定一张 $n$ 个点 $m$ 条边的无向连通图和这张图的一棵生成树 $T_1$，保证给定的图满足删掉任意一个点和它连接的所有边之后，这张图还是连通的。

现在你想要 $T_1$ 更换成图上的另外一棵生成树 $T_2$，你可以进行如下操作：

1. 选中 $T_1$ 中的一个叶子 $x$。
2. 选择原图上一个的点 $z\ (z \not= x)$ 满足 $z$ 和 $x$ 在原图上相连，将 $T_1$ 中的 $x$ 和它的父亲之间的边断开，然后连接 $x$ 和 $z$。

你想知道能否将 $T_1$ 变成 $T_2$，如果能，请你构造一个方案。

输入格式

第一行两个正整数 $n, m$ 表示图的点数和边数。

接下来 $m$ 行四个整数 $x, y, f_1, f_2$ 描述图上的一条边，$f_1, f_2$ 分别表示这条边是否在 $T_1, T_2$ 上。

输出格式

如果不能，输出 No。

否则第一行输出 Yes，第二行输出一个正整数 $k$ 表示操作步数。

接下来 $k$ 行，每行两个正整数 $x, z$，表示将 $x$ 和其父亲断开，然后连接 $x$ 和 $z$。

样例

样例 1

8 9
1 2 1 1
2 3 1 1
3 4 1 1
4 5 1 0
5 6 1 1
6 7 1 1
7 8 1 1
8 1 0 0
2 7 0 1

Yes
5
1 8
2 7
3 2
4 3
1 2

说明

本题使用 SPJ 进行评测。

下发文件中给出了 checker.cpp，使用方法是 ./checker <input-file> <output-file> <answer-file>。

如果输出文件的 Yes 或 No 和答案文件给出的不一致，checker 会给出 Wrong Answer [1]。

如果在你的某次输出中出现了 $z = x$ 的情况，会给出 Wrong Answer [2]。

如果在某次输出中 $x$ 不是叶子节点，会给出 Wrong Answer [3]。

如果 $(x, z)$ 这条边没有在原图上出现过，会给出 Wrong Answer [4]。

如果最后操作完的树不是 $T_2$，会给出 Wrong Answer [5]。

否则会给出 Accepted!。

测试点约束

对于 $100\%$ 的数据，$3\le n\le100$，$m\le \frac{n\times (n-1)}{2}$，保证图没有重边和自环。