#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=105; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,dep; set<int>v[maxn],v2[maxn],g[maxn]; vector<pi>opt; map<pi,int>EG; set<int>LF,LF2; int cnt[maxn],fa[maxn]; inline void dfs(int u,int father) { fa[u]=father; for(int x:v[u]){ if(x==father) continue; dfs(x,u); } } inline void dfs2(int u,int father) { fa[u]=father; for(int x:v2[u]){ if(x==father) continue; dfs2(x,u); } } struct HASH { long long p,mod; vector<int> vec; inline void init() { vec.clear(); for(int i=0;i<=n;i++) cnt[i]=0; } inline long long calc() { init(); for(int i=1;i<=n;i++) cnt[fa[i]]++; priority_queue<int,vector<int>,greater<int> > q; for(int i=1;i<=n;i++) if(cnt[i]==0) q.push(i); while(!q.empty()) { int u=q.top(); q.pop(); if(u==1)break; vec.push_back(fa[u]); cnt[fa[u]]--; if(cnt[fa[u]]==0) q.push(fa[u]); } long long t=0; for(int i=0;i<vec.size();i++) t=(t*p+1ll*vec[i])%mod; return t; } }h1,h2; pi cal(){ dfs(1,0); return m_p(h1.calc(),h2.calc()); } pi cal2(){ dfs2(1,0); return m_p(h1.calc(),h2.calc()); } map<pi,int>mp,mp2; map<pi,vector<pi> >mt; bool chk(){ up(i,1,n)for(int x:v[i])if(!EG.count(m_p(i,x)))return 0; return 1; } void dfs(int d){ auto it=cal(); if(mp.count(it))return; mp[it]=1; if(d>dep/2){ mt[it]=opt; return; } set<int>tmp=LF; for(int x:tmp){ int u=(*v[x].begin()); v[u].erase(x),v[x].erase(u); if(v[u].size()==1)LF.insert(u); for(int y:g[x]){ if(y==u)continue; if(v[y].size()==1)LF.erase(y); v[x].insert(y),v[y].insert(x); opt.p_b(m_p(x,y)); dfs(d+1); opt.pop_back(); v[x].erase(y),v[y].erase(x); if(v[y].size()==1)LF.insert(y); }if(v[u].size()==1)LF.erase(u); v[u].insert(x),v[x].insert(u); } } void dfs2(int d){ auto it=cal2(); if(mp2.count(it))return; mp2[it]=1; if(d>dep-dep/2){ if(!mt.count(it))return; printf("Yes\n%d\n",dep); for(auto it:mt[it])printf("%d %d\n",it.p1,it.p2); reverse(opt.begin(),opt.end()); for(auto it:opt)printf("%d %d\n",it.p1,it.p2); exit(0); return; } set<int>tmp=LF2; for(int x:tmp){ int u=(*v2[x].begin()); v2[u].erase(x),v2[x].erase(u); if(v2[u].size()==1)LF2.insert(u); for(int y:g[x]){ if(y==u)continue; if(v2[y].size()==1)LF2.erase(y); v2[x].insert(y),v2[y].insert(x); opt.p_b(m_p(x,u)); dfs2(d+1); opt.pop_back(); v2[x].erase(y),v2[y].erase(x); if(v2[y].size()==1)LF2.insert(y); }if(v2[u].size()==1)LF2.erase(u); v2[u].insert(x),v2[x].insert(u); } } void slv(){ n=read(),m=read(); int cg=0; up(i,1,m){ int x=read(),y=read(); g[x].insert(y),g[y].insert(x); int o1=read(),o2=read(); if(o1)v[x].insert(y),v[y].insert(x); if(o2)EG[m_p(x,y)]=EG[m_p(y,x)]=1,v2[x].insert(y),v2[y].insert(x); if(o1&&o2)cg++; } if(cg==n-1){ printf("Yes\n0\n");return; } up(i,1,n)if(v[i].size()==1)LF.insert(i); up(i,1,n)if(v2[i].size()==1)LF2.insert(i); while(1){ ++dep; mp.clear(),mp2.clear(),mt.clear(); dfs(1),dfs2(1); } }int main(){ h1.p=59,h1.mod=1e9+7; h2.p=131,h2.mod=998244353; slv(); fclose(stdin); fclose(stdout); return 0; }