#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair const int maxn=1e4+10; int n,m; struct node { int u,v,f1,f2; }ed[maxn]; int sed[110][110]; vector<int> edge[110]; set<int> st[maxn]; int fat[2][110],cnt[2][maxn]; void dfs(int u,int father,int stat) { for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(v==father) continue; fat[stat][v]=u; cnt[stat][u]++; dfs(v,u,stat); } } struct HASH { int p,mod; vector<int> vec,edge[110]; int cnt[maxn],fa[maxn]; void dfs(int u,int father) { fa[u]=father; for(set<int>::iterator it=st[u].begin();it!=st[u].end();it++) { int v=(*it); if(v==father) continue; dfs(v,u); } } void init() { vec.clear(); for(int i=0;i<=n;i++) cnt[i]=0,fa[i]=0; dfs(1,0); } int 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(); vec.push_back(fa[u]); cnt[fa[u]]--; if(cnt[fa[u]]==0) q.push(fa[u]); } int t=0; for(int i=0;i<vec.size();i++) t=(t*p+vec[i])%mod; return t; } int calcsp() { vec.clear(); for(int i=1;i<=n;i++) cnt[i]=0; for(int i=1;i<=n;i++) cnt[fat[1][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(); vec.push_back(fat[1][u]); cnt[fat[1][u]]--; if(cnt[fat[1][u]]==0) q.push(fat[1][u]); } int t=0; for(int i=0;i<vec.size();i++) t=(t*p+vec[i])%mod; return t; } }h1,h2; map<int,int> vis1,vis2; stack<pii> s; int ed1,ed2; void print() { cout<<"Yes"<<endl; vector<pii> ans; while(!s.empty()) { ans.push_back(s.top()); s.pop(); } cout<<ans.size()<<endl; for(int i=(int)ans.size()-1;i>=0;i--) cout<<ans[i].fi<<" "<<ans[i].se<<"\n"; cout<<endl; } int ct=0; inline void dfs() { if(h1.calc()==ed1&&h2.calc()==ed2) { print(); exit(0); } if(vis1[h1.calc()]&&vis2[h2.calc()]) return ; vis1[h1.calc()]=vis2[h2.calc()]=1; for(register int i=1;i<=n;i++) { if(st[i].size()>1) continue; int fa=(*st[i].begin()); for(int j=1;j<=n;j++) { if(i==j||j==fa||!sed[i][j]) continue; int tmp=fa; st[i].clear(),st[tmp].erase(i); st[j].insert(i),st[i].insert(j); s.push(mp(i,j)); dfs(); st[i].erase(j); st[j].erase(i); st[i].insert(tmp); st[tmp].insert(i); s.pop(); } } } signed main() { // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) cin>>ed[i].u>>ed[i].v>>ed[i].f1>>ed[i].f2,sed[ed[i].u][ed[i].v]=sed[ed[i].v][ed[i].u]=1; h1.p=199,h1.mod=1e9+7; h2.p=211,h2.mod=1011451423; for(int i=1;i<=n;i++) edge[i].clear(); for(int i=1;i<=m;i++) if(ed[i].f2==1) { edge[ed[i].u].push_back(ed[i].v); edge[ed[i].v].push_back(ed[i].u); } dfs(1,0,1); ed1=h1.calcsp(),ed2=h2.calcsp(); for(int i=1;i<=m;i++) if(ed[i].f1==1) { st[ed[i].u].insert(ed[i].v); st[ed[i].v].insert(ed[i].u); } dfs(); cout<<"No"<<endl; return 0; }