#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 109, M = 5009; struct Edge { int u, v; Edge(int uu = 0, int vv = 0) : u(uu), v(vv) {} } E[M]; int n, m, g[N][N]; vector<pair<int, int> > ans; struct DSU { int fa[N]; void init() {for (int i = 1; i <= n; i++) fa[i] = i;} int get(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } void merge(int x, int y) { x = get(x), y = get(y); if (x != y) fa[y] = x; } } dsu; struct Tree { bool g[N][N], vis[N]; int siz; Tree() {memset(g, 0, sizeof(g));} void build(Edge e1, Edge e2) { dsu.init(); int cnt = 0; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; if (g[u][v]) dsu.merge(u, v), cnt++; } g[e1.u][e1.v] = g[e1.v][e1.u] = 1, dsu.merge(e1.u, e1.v); g[e2.u][e2.v] = g[e2.v][e2.u] = 1, dsu.merge(e2.u, e2.v); cnt += 2; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v, fu = dsu.get(u), fv = dsu.get(v); if (fu != fv) { dsu.fa[fv] = fu, g[u][v] = g[v][u] = 1; if (++cnt == n - 1) return; } } } } T1, T2; bool vis[N]; void dfs(const Tree &T, int u, int &cnt) { if (vis[u]) return; vis[u] = 1, cnt++; for (int v = 1; v <= n; v++) { if (T.g[u][v]) dfs(T, v, cnt); } } Tree get(const Tree &x, const Tree &y) { Tree res; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; if (x.g[u][v] && y.g[u][v]) res.g[u][v] = res.g[v][u] = 1; } int mx = 0, id = 0; memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) { if (!vis[i]) { int cnt = 0; dfs(res, i, cnt); if (cnt > mx) mx = cnt, id = i; } } memset(vis, 0, sizeof(vis)); res.siz = mx, mx = 0, dfs(res, id, mx); memset(res.g, 0, sizeof(res.g)); for (int i = 1; i <= n; i++) res.vis[i] = vis[i]; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; if (vis[u] && vis[v] && x.g[u][v] && y.g[u][v]) res.g[u][v] = res.g[v][u] = 1; } return res; } void slv(const Tree &T1, const Tree &T2) { Tree T = get(T1, T2); if (T.siz == n) return; else if (T.siz == n - 1) { int u = 0; for (int i = 1; i <= n; i++) { if (!T.vis[i]) {u = i; break;} } for (int v = 1; v <= n; v++) { if (T2.g[u][v]) { ans.push_back(make_pair(u, v)); break; } } return; } Edge e1, e2; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; if (!e1.u && T.vis[u] + T.vis[v] == 1 && T1.g[u][v]) { if (T.vis[u]) e1 = Edge(v, u); else e1 = Edge(u, v); } if (!e2.u && T.vis[u] + T.vis[v] == 1 && T2.g[u][v]) { if (T.vis[u]) e2 = Edge(v, u); else e2 = Edge(u, v); } if (e1.u && e2.u) break; } if (e1.u != e2.u) { T.build(e1, e2); slv(T1, T), slv(T, T2); } else { Edge e3; for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; if (T.vis[u] + T.vis[v] == 1) { if (T.vis[u]) swap(u, v); if (u != e1.u) {e3 = Edge(u, v); break;} } } Tree _T = T; T.build(e1, e3), _T.build(e2, e3); slv(T1, T), slv(T, _T), slv(_T, T2); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v, f1, f2; scanf("%d%d%d%d", &u, &v, &f1, &f2); g[u][v] = g[v][u] = 1; if (f1) T1.g[u][v] = T1.g[v][u] = 1; if (f2) T2.g[u][v] = T2.g[v][u] = 1; E[i].u = u, E[i].v = v; } slv(T1, T2); printf("Yes\n%lld\n", ans.size()); for (auto e : ans) printf("%d %d\n", e.first, e.second); return 0; }