Cod sursa(job #56517)
using namespace std;
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <cassert>
#define NDEBUG
#define FIN "felinare.in"
#define FOUT "felinare.out"
#define maxn 8192
#ifndef NDEBUG
int stp;
#endif
vector<vector<short> > x;
char aa[maxn+2000][(maxn/8) +2000];
int n, m, E;
short source, sink;
short t[maxn<<1];
short d[maxn<<1];
bool Viz[maxn<<1];
int bfs();
void solve();
void read()
{
int i,p, q;
scanf("%d %d\n", &n, &m);
// a.clear();
// x.clear();
// a.resize(n+n+2);
// for(i=0;i<n+n+2;i++) a[i].resize(n+n+2);
source=0;
sink=n+n+1;
x.resize(n+n+2);
for(i=0;i<m;++i)
{
scanf("%d %d\n", &p, &q);
// a[p][q+n]=1;
aa[p][(q+n)>>3]|=(1<<((q+n)&7));
x[p].push_back(q+n);
x[q+n].push_back(p);
}
for(i=1;i<=n;++i)aa[source][i>>3]|=(1<<(i&7)), x[source].push_back(i), x[i].push_back(source);
for(i=n+1;i<sink;++i) aa[i][sink>>3]|=(1<<(sink&7)), x[i].push_back(sink), x[sink].push_back(i);
}
int bfs()
{
short Q[maxn<<1], p=1, q=1;
bool viz[maxn<<1];
memset(viz, 0,sizeof(viz));
//memset(t, -1, sizeof(t));
memset(d, 0, sizeof(d));
viz[source]=1;
Q[1]=source;
d[1]=0;
int u;
short i;
vector<short>::iterator it, xu;
while(p<=q)
{
u=Q[p++];
xu=x[u].end();
for(it=x[u].begin();it!=xu;++it)
{
i=*it;
if(!viz[i] && (aa[u][(i)>>3]&(1<<((i)&7))))
{
viz[i]=1;
d[i]=d[u]+1;
t[i]=u;
Q[++q]=i;
}
}
}
if(d[sink]==0) return 0;
return 1;
}
int flow, ok=1, dsink,nr;
void dfs2(short nd, short nr)
{
printf("%d %d\n",nd, nr);
if(nr>sink) return;
if(nd==sink) { ++flow; ok=0; return;}
if(nd==source) ok=1;
Viz[nd]=1;
vector<short>::iterator it, xnd;
short i;
xnd=x[nd].end();
for(it=x[nd].begin(); it!=xnd; ++it)
{
i=*it;
if(ok && !Viz[i] && ( aa[nd][(i)>>3]&(1<<((i)&7 ))))
{
//++nr;
dfs2(i, nr+1);
//--nr;
if(!ok)
{
aa[nd][(i)>>3]&=~(1<<((i)&7));
aa[i][nd>>3]|=(1<<(nd&7));
break;
}
}
}
}
void solve()
{
int i, j;
int p;
flow=0;
vector<short>::iterator it;
while(bfs())
{
memset(Viz, 0, sizeof(bool)*(sink+2));
//for(i=source;i<=sink;++i) Viz[i]=0;
ok=1;
nr=0;
dsink=d[sink];
dfs2(source, 0);
}
printf("%d\n", 2*n-flow);
}
int main()
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
read();
solve();
return 0;
}