1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
2 #include <cstdio>//sprintf islower isupper
3 #include <cstdlib>//malloc exit strcat itoa system("cls")
4 #include <iostream>//pair
5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
6 #include <bitset>
7 //#include <map>
8 //#include<unordered_map>
9 #include <vector>
10 #include <stack>
11 #include <set>
12 #include <string.h>//strstr substr
13 #include <string>
14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
15 #include <cmath>
16 #include <deque>
17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
18 #include <vector>//emplace_back
19 //#include <math.h>
20 #include <cassert>
21 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
22 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
23 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
24 //******************
25 int abss(int a);
26 int lowbit(int n);
27 int Del_bit_1(int n);
28 int maxx(int a,int b);
29 int minn(int a,int b);
30 double fabss(double a);
31 void swapp(int &a,int &b);
32 clock_t __STRAT,__END;
33 double __TOTALTIME;
34 void _MS(){__STRAT=clock();}
35 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
36 //***********************
37 #define rint register int
38 #define fo(a,b,c) for(rint a=b;a<=c;++a)
39 #define fr(a,b,c) for(rint a=b;a>=c;--a)
40 #define mem(a,b) memset(a,b,sizeof(a))
41 #define pr printf
42 #define sc scanf
43 #define ls rt<<1
44 #define rs rt<<1|1
45 typedef vector<int> VI;
46 typedef long long ll;
47 const double E=2.718281828;
48 const double PI=acos(-1.0);
49 //const ll INF=(1LL<<60);
50 const int inf=(1<<30);
51 const double ESP=1e-9;
52 const int mod=(int)1e9+7;
53 const int N=(int)2e5+10;
54
55 class DINIC
56 {
57 public:
58 // const int MAXN=10004,MAXWAY=100005;
59 int n,way,max_flow,deep[N];
60 int tot,head[N],cur[N];
61 struct EDGE{
62 int to,next;
63 int dis;
64 }edge[N];
65 void Init(int n)
66 {
67 tot=-1;//因为加反向边要^1,所以要从0开始;
68 this->n=n;
69 for(int i=0;i<=n;++i)
70 head[i]=-1;
71 }
72 void add(int from,int to,int V,bool flag)
73 {
74 ++tot;
75 edge[tot].to=to;
76 edge[tot].dis=0;
77 if(flag)edge[tot].dis=V;
78 edge[tot].next=head[from];
79 head[from]=tot;
80 }
81 queue<int>q;
82 bool bfs(int s,int t)
83 {
84 for(int i=1;i<=n;++i)
85 deep[i]=inf;
86 while(!q.empty())q.pop();
87 for(int i=1;i<=n;++i)cur[i]=head[i];
88 deep[s]=0;
89 q.push(s);
90
91 while(!q.empty())
92 {
93 int now=q.front();q.pop();
94 for(int i=head[now];i!=-1;i=edge[i].next)
95 {
96 if(deep[edge[i].to]==inf&&edge[i].dis)
97 {
98 deep[edge[i].to]=deep[now]+1;
99 q.push(edge[i].to);
100 }
101 }
102 }
103 return deep[t]<inf;
104 }
105 int dfs(int now,int t,int limit)
106 {
107 if(!limit||now==t)return limit;
108 int flow=0,f;
109 for(int i=cur[now];i!=-1;i=edge[i].next)
110 {
111 cur[now]=i;
112 if(deep[edge[i].to]==deep[now]+1&&(f=dfs(edge[i].to,t,min(limit,edge[i].dis))))
113 {
114 flow+=f;
115 limit-=f;
116 edge[i].dis-=f;
117 edge[i^1].dis+=f;
118 if(!limit)break;
119 }
120 }
121 return flow;
122 }
123 void Dinic(int s,int t)
124 {
125 while(bfs(s,t))
126 max_flow+=dfs(s,t,inf);
127 }
128 }G;
129
130 int main()
131 {
132 int m,n;
133 sc("%d%d",&m,&n);
134 int u,v,cnt=0;
135 G.Init(n+2);
136 while(sc("%d%d",&u,&v),u!=-1&&v!=-1)
137 {
138 u++,v++;
139 cnt++;
140 G.add(u,v,1,1);G.add(v,u,1,0);
141 }
142 cnt*=3;
143 for(int i=2;i<=m+1;++i)
144 {
145 G.add(1,i,1,1);
146 G.add(i,1,1,0);
147 }
148 for(int i=m+2;i<=n+1;++i)
149 {
150 G.add(i,n+2,1,1);
151 G.add(n+2,i,1,0);
152 }
153 G.Dinic(1,n+2);
154 pr("%d
",G.max_flow);
155 for(int i=1,j=0;i<=cnt;++i,j+=2)
156 {
157 if(G.edge[j].to!=1&&G.edge[j+1].to!=1)
158 if(G.edge[j].to!=n+2&&G.edge[j+1].to!=n+2)
159 if(G.edge[j+1].dis)//网络流可以判断正向边是否有流量（即反向边的残量是否不为 0）
160 {
161 pr("%d %d
",G.edge[j+1].to-1,G.edge[j].to-1);
162 }
163 }
164 return 0;
165 }
166
167 /**************************************************************************************/
168
169 int maxx(int a,int b)
170 {
171 return a>b?a:b;
172 }
173
174 void swapp(int &a,int &b)
175 {
176 a^=b^=a^=b;
177 }
178
179 int lowbit(int n)
180 {
181 return n&(-n);
182 }
183
184 int Del_bit_1(int n)
185 {
186 return n&(n-1);
187 }
188
189 int abss(int a)
190 {
191 return a>0?a:-a;
192 }
193
194 double fabss(double a)
195 {
196 return a>0?a:-a;
197 }
198
199 int minn(int a,int b)
200 {
201 return a<b?a:b;
202 }