Cod sursa(job #299928)
#include <stdio.h>
#define N 105
using namespace std;
int flux[N<<1][N<<1];
int inc,sf,n,m,S,D;
int Q[N],tati[N];
int pl[N],in[N],numar;
void citire()
{
freopen ("harta.in","r",stdin);
freopen ("harta.out","w",stdout);
scanf ("%d",&n);
for (int i=1;i<=n;i++)
scanf ("%d %d",&pl[i],&in[i]);
S=0;
D=2*n+1;
}
void init()
{
for (int i=1;i<=n;i++)
flux[S][i]=pl[i];
for (int i=1;i<=n;i++)
flux[i+n][D]=in[i];
for (int i=1;i<=n;i++)
for (int j=n+1;j<=n<<1;j++)
if (i!=j-n)
flux[i][j]=1;
}
int bell()
{
int n1;
for (int i=1;i<=(n<<1)+1;i++)
tati[i]=-1;
inc=0;
sf=1;
Q[0]=S;
tati[S]=0;
while (inc<sf)
{
n1=Q[inc++];
for (int i=1;i<=D;i++)
if (flux[n1][i] && tati[i]==-1)
{
tati[i]=n1;
Q[sf++]=i;
}
if (tati[D]!=-1)
return 1;
}
return 0;
}
void fl()
{
int poz;
while (bell())
{
poz=D;
while (poz!=S)
{
flux[tati[poz]][poz]--;
flux[poz][tati[poz]]++;
poz=tati[poz];
}
numar++;
}
}
void afish()
{
printf("%d\n",numar);
for (int i=1;i<=n;i++)
for (int j=n+1;j<=n<<1;j++)
if (!flux[i][j] && i!=j-n)
printf("%d %d\n",i,j-n);
}
int main ()
{
citire();
init();
fl();
afish();
return 0;
}