### Saratov State University :: Online Contester

::Go
- home
- news
- register
 - update personal info
 - problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- projects

 ::Poll Are you registered on Codeforces?YesNoWhat is it???[results]

::webboard

 why wrong on 23
Author: ata
ID: 059912
Problem: 190
Contest: 0
Date: 2014-09-17 16:21:01

#include<bits/stdc++.h>

using namespace std;

const int Maxn=40*40+10;

int n,p,c,matchl[Maxn],matchr[Maxn],cv,ch;
vector<int> com[2];
vector<pair<int,int> >ans[2];

inline void init()
{
for(int i=0;i<n*n;i++)
{
if(i>n-1)
if(i<n*(n-1))
if(i%n!=n-1)
if(i%n!=0)
}
}

void ca(int t1)
{
if(t1>n-1)
if(t1<n*(n-1))
if(t1%n!=0)
if(t1%n!=n-1)
}

inline void input()
{
cin>>n>>p;
init();
for(int i=0;i<p;i++)
{
int t1,t2;
cin>>t1>>t2;
t1=t1-1+(t2-1)*n;
//cerr<<t1<<endl;
mark[t1]=true;
ca(t1);
}
}

void DFS(int v,bool w)
{
mark[v]=true;
com[w].push_back(v);
for(int i=0;i<n*n;i++)
DFS(i,!w);
}

bool check()
{
for(int i=0;i<n*n;i++)
if(!mark[i])
{
//cerr<<i<<endl;
DFS(i,0);
if(com[0].size()!=com[1].size())
return false;
}
return true;
}

bool match(int v)
{
for(int i=0;i<n*n;i++)
{
if(mark[i])
continue;
mark[i]=true;
if(matchr[i]==-1||match(matchr[i]))
{
matchl[v]=i;
matchr[i]=v;
return true;
}
}
return false;
}

inline void make_match()
{
for(int i=0;i<com[0].size();i++)
if(matchl[com[0][i]]==-1)
{
memset(mark,0,sizeof mark);
match(com[0][i]);
}
}

inline void count()
{
for(int i=0;i<com[0].size();i++)
if(com[0][i]%n==matchl[com[0][i]]%n)
{
cv++;
int t1=min(com[0][i],matchl[com[0][i]]);
ans[1].push_back(make_pair(t1%n+1,t1/n+1));
}
else
{
ch++;
int t1=min(com[0][i],matchl[com[0][i]]);
ans[0].push_back(make_pair(t1%n+1,t1/n+1));
}
}

inline void solve()
{
if(!check())
return ;
memset(mark,0,sizeof mark);
for(int i=0;i<n*n;i++)
matchl[i]=matchr[i]=-1;
make_match();
count();

}

inline void output()
{
if(com[0].size()!=com[1].size())
{
cout<<"Non";
return;
}

cout<<"Yesn"<<ch<<endl;
for(int i=0;i<ch;i++)
cout<<ans[0][i].first<<" "<<ans[0][i].second<<endl;
cout<<cv<<endl;
for(int i=0;i<cv;i++)
cout<<ans[1][i].first<<" "<<ans[1][i].second<<endl;
}

/*inline void output()
{
for(int i=0;i<com[0].size();i++)
cerr<<com[0][i]<<" "<<matchl[com[0][i]]<<endl;
}*/

int main()
{
input();
solve();
output();
return 0;
}