```cpp
#include<cstdio>
#include<queue>
using namespace std;
int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*f;
}
void wr(int s)
{
if(s<0)putchar('-'),s=-s;
if(s>9)wr(s/10);
putchar(s%10+48);
}
const int inf=1e3+7;
int nl,nr,s,t,ans;
int fir[inf],nex[inf<<1],poi[inf<<1],val[inf<<1],cnt=1;
void ins(int x,int y,int z)
{
nex[++cnt]=fir[x];
poi[cnt]=y;
val[cnt]=z;
fir[x]=cnt;
}
int dep[inf];
bool bfs()
{
for(int i=0;i<=nr+nl+1;i++)
dep[i]=0x7f7f7f7f;
queue<int>h;
h.push(s);dep[s]=0;
while(h.size())
{
int now=h.front();h.pop();
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(val[i]==0)continue;
if(dep[p]==0x7f7f7f7f)
{
dep[p]=dep[now]+1;
h.push(p);
}
}
}
return !(dep[t]==0x7f7f7f7f);
}
int dfs(int now,int minn)
{
if(now==t)return minn;
int sum=0;
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(val[i]==0||dep[p]!=dep[now]+1)continue;
int ls=dfs(p,min(minn,val[i]));
if(ls==0)continue;
val[i]-=ls,val[i^1]+=ls;
sum+=ls,minn-=ls;
if(minn==0)break;
}
return sum;
}
int main()
{
nl=re(),nr=re()-nl;
s=0,t=nl+nr+1;
while(1)
{
int u=re(),v=re();
if(u==-1&&v==-1)break;
ins(u,v,0x3f3f3f3f);
ins(v,u,0);
}
for(int i=1;i<=nl;i++)
ins(s,i,1),ins(i,s,0);
for(int i=nl+1;i<=nl+nr;i++)
ins(i,t,1),ins(t,i,0);
while(1)
{
if(bfs()==0)break;
ans+=dfs(s,2147483647);
}
wr(ans);putchar('\n');
for(int i=1;i<=nl;i++)
{
for(int j=fir[i];j;j=nex[j])
{
if(val[j]==0x3f3f3f3f-1&&poi[j])
{
wr(i),putchar(' ');
wr(poi[j]),putchar('\n');
break;
}
}
}
return 0;
}
```
by Zvelig1205 @ 2022-08-07 17:46:42
input
```text
18 37
13 20
1 22
2 22
4 29
3 35
9 33
17 31
17 29
4 22
8 33
9 37
18 21
18 25
18 36
15 36
6 32
15 19
4 35
8 23
15 24
15 29
5 31
9 36
12 22
14 27
10 32
14 24
15 27
6 25
10 35
12 29
14 26
10 36
17 27
18 19
8 32
5 20
3 27
4 28
1 25
18 23
9 34
8 25
6 22
6 27
13 26
14 35
11 36
18 28
2 26
12 24
15 31
8 23
17 19
7 25
17 27
5 36
9 35
4 32
5 21
15 19
13 26
13 28
13 37
18 34
1 22
3 34
17 24
5 32
11 29
9 34
13 33
3 36
9 37
2 32
12 37
2 28
11 29
13 26
18 24
2 34
12 28
1 37
18 25
11 34
1 23
11 32
11 28
7 29
3 20
4 36
2 21
18 20
14 32
11 20
10 20
18 33
14 25
11 30
2 33
16 25
5 20
12 34
3 31
2 23
16 26
17 26
1 29
8 30
18 26
14 33
15 21
16 35
12 29
4 19
6 29
15 31
15 21
9 24
11 27
13 28
14 19
16 29
1 26
10 31
16 27
12 33
5 22
7 25
7 34
2 19
2 24
15 28
13 36
13 27
3 32
8 32
6 21
7 27
4 24
13 28
3 25
9 23
8 20
3 28
16 23
12 22
9 23
6 32
13 31
11 21
9 31
12 19
14 35
11 22
9 22
1 34
1 28
6 31
2 27
2 19
4 24
11 32
16 36
16 32
17 32
6 28
10 25
11 37
4 23
4 32
13 20
7 27
3 31
14 23
4 36
16 29
10 32
14 26
14 33
5 35
2 25
7 27
17 23
8 21
4 29
17 30
3 27
16 24
2 27
9 24
12 20
5 22
17 31
8 37
8 24
17 19
12 23
15 31
15 25
6 35
17 33
1 19
7 19
18 24
16 37
17 19
14 30
7 28
8 19
10 19
16 21
16 20
1 32
14 30
13 21
2 27
17 19
5 32
15 34
4 35
4 31
5 30
5 28
16 27
17 31
16 33
7 30
13 27
12 34
10 33
18 21
14 23
2 26
14 35
11 19
5 30
5 26
1 23
11 19
17 28
16 25
10 34
2 29
13 20
10 36
11 36
16 26
5 25
10 32
8 34
12 21
7 33
6 30
13 21
14 31
13 23
7 23
7 21
9 28
7 22
7 24
7 29
16 23
16 34
16 33
10 36
10 33
14 36
17 31
9 21
12 33
10 23
11 22
4 27
2 34
4 25
18 36
11 30
17 33
1 32
12 26
1 35
18 22
16 22
17 30
2 33
18 31
15 20
18 36
3 23
4 27
6 27
12 35
14 24
5 24
13 27
12 27
10 37
16 36
3 22
6 21
10 24
7 23
12 22
4 22
8 26
3 21
13 35
7 23
10 35
13 29
18 35
10 37
4 20
3 28
18 20
18 24
18 31
5 21
7 26
16 24
13 28
10 28
15 31
11 36
18 30
16 24
8 25
11 33
7 20
4 22
8 21
14 31
16 20
6 30
16 37
12 19
12 35
10 34
14 25
2 37
3 22
8 31
3 31
3 23
2 37
9 36
5 37
15 33
12 29
15 25
4 33
4 37
14 33
11 19
7 25
16 35
18 36
15 31
13 27
5 35
16 29
10 19
9 33
7 21
14 29
4 25
18 24
12 32
3 19
14 33
8 28
6 22
15 34
10 24
5 32
9 23
18 33
3 27
16 24
9 34
6 37
13 30
14 20
18 26
7 27
5 23
3 23
4 20
5 27
11 33
10 30
7 20
14 26
4 35
15 20
10 31
5 30
17 36
15 33
6 28
9 31
16 31
2 30
14 28
10 30
10 21
15 32
1 19
6 24
12 26
5 25
1 19
15 23
3 22
10 36
9 28
9 37
3 28
7 25
17 22
14 36
7 30
6 26
12 29
8 28
18 32
5 23
9 37
12 22
17 30
14 26
9 36
7 25
11 25
4 24
18 36
4 29
14 36
3 37
1 27
3 23
8 23
2 34
12 25
9 28
17 22
10 28
6 19
2 24
13 22
10 25
17 23
9 36
3 37
6 22
17 35
11 35
13 32
17 25
15 22
16 20
1 27
9 23
11 32
4 19
18 28
9 31
4 33
6 29
4 23
10 23
8 32
7 30
8 37
18 37
11 32
15 37
5 36
9 30
17 35
3 21
10 21
9 22
14 33
10 35
9 33
11 36
17 23
7 19
12 35
6 35
13 22
10 30
2 25
15 22
12 30
10 34
13 21
12 21
7 31
9 26
3 36
5 29
15 34
13 37
18 26
8 36
6 22
13 34
6 29
3 24
6 29
13 28
2 29
3 22
12 32
1 24
16 25
17 35
17 35
10 35
8 21
18 34
11 21
15 20
6 25
17 23
10 36
6 37
14 20
5 23
5 28
2 37
5 26
2 22
18 33
15 33
15 19
3 23
1 34
2 36
5 30
10 29
12 29
10 22
12 36
1 32
6 23
17 31
11 35
5 33
4 33
10 28
4 35
9 28
14 20
3 25
12 19
16 23
13 25
2 31
9 22
15 19
15 27
5 21
16 27
1 26
18 27
16 20
9 29
13 30
6 30
3 30
6 36
17 28
2 31
13 29
4 33
9 22
2 24
2 27
15 29
6 33
2 28
4 22
18 22
2 20
15 27
15 34
7 31
16 19
9 24
13 33
6 24
1 22
11 36
14 27
5 24
1 31
13 31
3 35
13 30
1 36
10 36
7 32
4 25
16 29
2 33
6 20
12 34
15 20
1 28
3 37
12 37
14 30
10 37
5 37
13 29
14 19
18 32
5 34
3 20
15 22
7 22
15 37
16 22
3 22
18 20
3 37
2 23
6 35
1 30
8 31
13 30
18 34
7 25
17 23
18 24
9 37
4 32
4 34
8 26
6 24
5 22
5 24
6 37
15 31
7 21
5 24
7 25
5 31
6 20
1 29
5 30
13 27
16 37
18 25
10 22
3 23
18 27
15 21
1 19
13 31
3 32
14 36
4 20
4 24
18 30
9 21
17 21
18 21
12 31
4 21
1 37
16 26
1 30
11 33
3 31
3 19
3 30
6 34
1 33
4 33
5 29
12 19
18 29
9 35
3 23
8 33
16 37
8 20
12 30
14 19
6 24
3 22
5 19
15 32
15 22
10 27
15 34
7 37
11 19
3 28
5 25
1 30
4 35
1 20
10 28
3 22
4 32
17 26
2 24
3 31
18 23
4 26
15 28
10 36
5 29
1 28
13 19
17 20
11 29
14 23
1 37
2 25
17 29
6 24
1 36
5 35
4 21
14 34
4 31
18 23
9 28
17 28
18 23
14 27
11 34
3 21
16 28
4 32
5 31
17 33
3 21
13 26
9 30
3 19
5 21
13 31
5 23
10 29
4 37
1 30
16 32
11 26
17 36
17 22
4 21
5 37
3 33
12 25
12 34
3 28
13 34
9 30
17 34
5 20
12 25
2 28
10 24
12 33
4 31
11 23
9 37
12 36
16 30
17 19
6 35
14 36
12 31
14 32
10 24
9 34
6 36
9 36
15 26
7 33
10 21
6 23
7 34
1 22
7 27
15 21
6 29
5 34
13 20
8 27
17 24
8 21
3 27
16 32
11 26
7 31
1 24
12 35
17 29
16 36
16 24
9 36
4 29
4 27
13 28
17 24
14 29
17 34
2 32
15 19
13 25
13 22
13 23
15 27
12 21
11 21
10 29
17 25
6 20
15 30
12 36
10 29
8 19
15 37
11 19
1 36
5 21
2 37
16 29
1 34
1 31
2 27
14 19
13 31
8 27
1 22
14 26
6 37
12 28
2 20
15 32
2 25
1 19
5 23
16 23
3 20
9 21
10 26
14 29
9 30
11 35
2 24
6 28
16 25
12 19
5 31
18 29
10 29
16 22
13 33
2 32
15 33
13 31
4 28
1 25
15 29
8 37
11 32
12 26
1 22
14 35
16 30
10 37
18 34
3 21
8 28
6 20
10 32
18 37
18 36
11 19
13 23
1 34
17 22
7 34
13 31
4 19
4 19
10 20
2 27
16 22
1 23
1 26
15 36
9 36
12 30
1 37
9 34
2 28
5 26
18 20
13 19
2 28
8 24
13 27
13 36
18 23
18 36
2 25
13 35
15 27
3 21
5 30
11 20
13 20
11 22
7 28
14 34
5 35
8 28
5 27
17 24
17 36
17 30
7 19
18 29
18 37
17 19
13 20
10 37
15 22
12 21
13 32
10 34
1 36
10 23
8 20
4 25
14 23
7 23
16 26
1 32
6 27
11 26
17 34
3 26
2 37
10 28
18 36
16 37
16 22
14 21
16 24
1 23
2 27
7 23
13 37
8 37
18 20
12 20
2 19
5 29
-1 -1
```
output
```text
18
1 37
2 36
3 35
4 34
5 33
6 31
7 30
8 28
9 21
10 19
11 20
12 22
13 23
14 29
15 32
16 27
17 25
18 24
```
by Zvelig1205 @ 2022-08-07 17:51:19
0. （O2 挂了，洛谷 IDE 上 C++14 GCC9 亲测能过这组数据
1. Dinic 把当前弧优化写一下
2. 边数极限会是 (50×50+50+50)×2=5400 条的
by Francais_Drake @ 2022-08-07 20:20:57
@[Francais_Drake](/user/546086) 为什么我加上当前弧就错了……
by Zvelig1205 @ 2022-08-07 20:24:28
加了当前弧本地也过不了了
by Zvelig1205 @ 2022-08-07 20:25:21
边调大了就A了……我是**
by Zvelig1205 @ 2022-08-07 20:25:42
此处指开 O2 的情况下会玄学挂掉。
对，你数组开小了，你的代码在这组数据上会加 $2017$ 条边，而你只开了 $2013$ 条边的空间，导致 `fir[0]` 被覆盖成某个错误的值。
by Francais_Drake @ 2022-08-07 20:34:25
哦你提前发现了
by Francais_Drake @ 2022-08-07 20:35:24
我wa在第6组数据，有大佬可以提供一下第六组数据？
by up001 @ 2022-08-30 17:08:53
@[up001](/user/783390) 可以自己下载
by Zvelig1205 @ 2022-08-30 18:30:31