1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| #include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 10005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int s,t,n,m;
vector<int>to[maxn];
int head=1,h[maxn],c[maxn];
void dfs(int x,int color) {
int i;
c[x]=color;
for (auto y:to[x])
if (!c[y]) dfs(y,3-color);
}
struct yyy {
int to,z,w;
void add(int x,int y,int val) {
to=y;z=h[x];h[x]=head;w=val;
}
}a[300005];
void ins(int x,int y,int z) {
a[++head].add(x,y,z);
a[++head].add(y,x,0);
}
const int inf=1e16;
pair<int,int> Ans[maxn];
int cnt;
namespace Dinic {
int deep[maxn],now[maxn];
queue<int>q;
bool bfs(void) {
int i,x;
memset(deep,-1,sizeof(deep));
deep[s]=1;q.push(s);
while (!q.empty()) {
x=q.front();q.pop();now[x]=h[x];
for (i=h[x];i;i=a[i].z) if (a[i].w&&deep[a[i].to]==-1) {
deep[a[i].to]=deep[x]+1;
q.push(a[i].to);
}
}
return deep[t]!=-1;
}
int dfs(int x,int in) {
if (!in||x==t) return in;
int i,sum,res=in;
for (i=now[x];i&&res;i=a[i].z) {
now[x]=i;
if (a[i].w&&deep[a[i].to]==deep[x]+1) {
sum=dfs(a[i].to,min(res,a[i].w));
if (!sum) deep[a[i].to]=-1;
a[i].w-=sum,res-=sum,a[i^1].w+=sum;
}
}
return in-res;
}
int dinic(void) {
int ans=0;
while (bfs()) ans+=dfs(s,inf);
return ans;
}
}
int dfn[maxn],low[maxn],stac[maxn],tot,times,vis[maxn],dccnums,dcc[maxn],siz[maxn];
void tarjan(int x,int pre) {
int i;
dfn[x]=low[x]=++times;stac[++tot]=x;vis[x]=1;
for (i=h[x];i;i=a[i].z) if (a[i].w) {
if (!dfn[a[i].to]) {
tarjan(a[i].to,x);
low[x]=min(low[x],low[a[i].to]);
}
else if (vis[a[i].to]) low[x]=min(low[x],dfn[a[i].to]);
}
if (low[x]==dfn[x]) {
++dccnums;
while (1) {
vis[stac[tot]]=0;
dcc[stac[tot]]=dccnums;
siz[dccnums]++;
if (stac[tot--]==x) break ;
}
}
}
signed main(void){
freopen("1.in","r",stdin);
int i,x,y;
read(n);read(m);
for (i=1;i<=m;i++) {
read(x),read(y);
to[x].push_back(y);
to[y].push_back(x);
}
s=0,t=n+1;
for (i=1;i<=n;i++) if (!c[i]) dfs(i,1);
for (i=1;i<=n;i++)
if (c[i]==1) {
ins(s,i,1);
}
else {
ins(i,t,1);
}
for (i=1;i<=n;i++)
for (auto y:to[i])
if (c[i]==1&&c[y]==2)
ins(i,y,1);
int tmp=Dinic::dinic();
for (i=0;i<=n+1;i++) if (!dfn[i]) tarjan(i,0);
for (i=2;i<=head;i+=2) {
x=a[i^1].to,y=a[i].to;
if (a[i].w==0&&dcc[x]!=dcc[y]&&x!=s&&y!=t) {
Ans[++cnt]=mk(x,y);
}
}
for (i=1;i<=cnt;i++) if (Ans[i].fi>Ans[i].se) swap(Ans[i].fi,Ans[i].se);
sort(Ans+1,Ans+1+cnt);
printf("%lld\n",cnt);
for (i=1;i<=cnt;i++) printf("%lld %lld\n",Ans[i].fi,Ans[i].se);
return 0;
}
|