#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
class Negot{
private:
struct elem
{
int x,poz;
};
vector<elem>a[41005];
elem tata[41005];
int n,s,d,sol,r[500002];
bool viz[41005];
queue<int>q;
public:
inline bool bfs()
{
int i,x,l;
for(i=1;i<=n;i++)
viz[i]=0,tata[i]={0,0};
q.push(s);
viz[s]=1;
while(!q.empty())
{
x=q.front();
q.pop();
l=a[x].size();
for(i=0;i<l;i++)
if(viz[a[x][i].x]==0&&r[a[x][i].poz]>0)
{
viz[a[x][i].x]=1;
tata[a[x][i].x].x=x;
tata[a[x][i].x].poz=a[x][i].poz;
q.push(a[x][i].x);
}
}
return viz[d];
}
inline void flux_maxim()
{
int i,j,flow,l=a[d].size();
while(bfs()!=0)
{
for(i=0;i<l;i++)
if(tata[a[d][i].x].x!=0&&r[a[d][i].poz^1]>0)
{
flow=r[a[d][i].poz^1];
for(j=a[d][i].x;j!=s;j=tata[j].x)
{
flow=min(flow,r[tata[j].poz]);
if(flow==0)
break;
}
if(flow!=0)
{
r[a[d][i].poz^1]-=flow;
r[a[d][i].poz]+=flow;
for(j=a[d][i].x;j!=s;j=tata[j].x)
{
r[tata[j].poz]-=flow;
r[tata[j].poz^1]+=flow;
}
sol+=flow;
}
}
}
}
void solution(){
ifstream f("negot.in");
ofstream g("negot.out");
int m,i,x,y,k=0,K,t,j;
f>>n>>m>>K;
for(i=1;i<=n;i++)
{
x=i;
f>>t;
for(j=1;j<=t;j++)
{
f>>y;
y+=n;
r[k]=1;
a[x].push_back({y,k});
k++;
r[k]=0;
a[y].push_back({x,k});
k++;
}
}
s=n+m+1;
d=n+m+2;
for(i=1;i<=n;i++)
{
r[k]=K;
a[s].push_back({i,k});
k++;
r[k]=0;
a[i].push_back({s,k});
k++;
}
for(i=n+1;i<=n+m;i++)
{
r[k]=1;
a[i].push_back({d,k});
k++;
r[k]=0;
a[d].push_back({i,k});
k++;
}
n=n+m+2;
flux_maxim();
g<<sol;
}
};
class Cc{
private:
struct nod
{
int x,poz;
};
vector<nod>a[205];
nod tata[205];
int n,s,d,flux,sol,r[20402],z[20402],dist[205],dist2[205],realdist[205];
bool inq[205];
queue<int>q;
struct elem
{
int x,dist;
inline bool operator < (const elem &a) const
{
return dist>a.dist;
}
};
priority_queue<elem>pq;
public:
inline bool dijkstra()
{
int i,l,Z;
elem p;
for(i=1;i<=n;i++)
dist[i]=INF,tata[i]={0,0};
pq.push({s,0});
dist[s]=0;
dist2[s]=0;
while(!pq.empty())
{
p=pq.top();
pq.pop();
if(p.dist==dist[p.x])
{
l=a[p.x].size();
for(i=0;i<l;i++)
{
Z=realdist[p.x]-realdist[a[p.x][i].x]+z[a[p.x][i].poz];
if(r[a[p.x][i].poz]>0&&dist[a[p.x][i].x]>dist[p.x]+Z)
{
dist[a[p.x][i].x]=dist[p.x]+Z;
dist2[a[p.x][i].x]=dist2[p.x]+z[a[p.x][i].poz];
tata[a[p.x][i].x].x=p.x;
tata[a[p.x][i].x].poz=a[p.x][i].poz;
pq.push({a[p.x][i].x,dist[a[p.x][i].x]});
}
}
}
}
for(i=1;i<=n;i++)
realdist[i]=dist2[i];
return dist[d]!=INF;
}
inline void bellman_ford()
{
int i,l,p;
for(i=1;i<=n;i++)
realdist[i]=INF;
realdist[s]=0;
q.push(s);
inq[s]=1;
while(!q.empty())
{
p=q.front();
q.pop();
inq[p]=0;
l=a[p].size();
for(i=0;i<l;i++)
if(r[a[p][i].poz]>0&&realdist[a[p][i].x]>realdist[p]+z[a[p][i].poz])
{
realdist[a[p][i].x]=realdist[p]+z[a[p][i].poz];
if(inq[a[p][i].x]==0)
{
q.push(a[p][i].x);
inq[a[p][i].x]=1;
}
}
}
}
inline void fmcm()
{
int i,flow,cost;
bellman_ford();
while(dijkstra()!=0)
{
flow=INF;
for(i=d;i!=s;i=tata[i].x)
{
flow=min(flow,r[tata[i].poz]);
if(flow==0)
break;
}
if(flow!=0&&flow!=INF)
{
cost=0;
for(i=d;i!=s;i=tata[i].x)
{
r[tata[i].poz]-=flow;
r[tata[i].poz^1]+=flow;
cost+=z[tata[i].poz];
}
flux+=flow;
sol+=flow*cost;
}
}
}
void solution()
{
ifstream f("cc.in");
ofstream g("cc.out");
int i,x,k=0,j;
f>>n;
s=2*n+1;
d=2*n+2;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
f>>x;
r[k]=1;
z[k]=x;
a[i].push_back({j+n,k});
k++;
r[k]=0;
z[k]=-x;
a[j+n].push_back({i,k});
k++;
}
for(i=1;i<=n;i++)
{
r[k]=1;
z[k]=0;
a[s].push_back({i,k});
k++;
r[k]=0;
z[k]=0;
a[i].push_back({s,k});
k++;
r[k]=1;
z[k]=0;
a[i+n].push_back({d,k});
k++;
r[k]=0;
z[k]=0;
a[d].push_back({i+n,k});
k++;
}
n=n*2+2;
fmcm();
g<<sol;
}
};
class Senat{
private:
struct elem
{
int x,poz;
};
vector<elem>a[205];
elem tata[205];
int n,s,d,sol,r[40002];
bool viz[205];
queue<int>q;
char ss[20002];
public:
inline bool bfs()
{
int i,x,l;
for(i=1;i<=n;i++)
viz[i]=0,tata[i]={0,0};
q.push(s);
viz[s]=1;
while(!q.empty())
{
x=q.front();
q.pop();
l=a[x].size();
for(i=0;i<l;i++)
if(viz[a[x][i].x]==0&&r[a[x][i].poz]>0)
{
viz[a[x][i].x]=1;
tata[a[x][i].x].x=x;
tata[a[x][i].x].poz=a[x][i].poz;
q.push(a[x][i].x);
}
}
return viz[d];
}
inline void flux_maxim()
{
int i,j,flow,l=a[d].size();
while(bfs()!=0)
{
for(i=0;i<l;i++)
if(tata[a[d][i].x].x!=0&&r[a[d][i].poz^1]>0)
{
flow=r[a[d][i].poz^1];
for(j=a[d][i].x;j!=s;j=tata[j].x)
{
flow=min(flow,r[tata[j].poz]);
if(flow==0)
break;
}
if(flow!=0)
{
r[a[d][i].poz^1]-=flow;
r[a[d][i].poz]+=flow;
for(j=a[d][i].x;j!=s;j=tata[j].x)
{
r[tata[j].poz]-=flow;
r[tata[j].poz^1]+=flow;
}
sol+=flow;
}
}
}
}
void solution()
{
ifstream f("senat.in");
ofstream g("senat.out");
int m,i,x,k=0,j,l,nn;
f>>n>>m;
nn=n;
f.get();
for(j=1;j<=m;j++)
{
f.getline(ss+1,20001);
i=1;
l=strlen(ss+1);
while(i<=l)
{
while(i<=l&&ss[i]==' ')
i++;
x=0;
while(i<=l&&ss[i]!=' ')
x=x*10+ss[i]-48,i++;
r[k]=1;
a[j+n].push_back({x,k});
k++;
r[k]=0;
a[x].push_back({j+n,k});
k++;
}
}
s=n+m+1;
d=n+m+2;
for(i=1;i<=n;i++)
{
r[k]=1;
a[i].push_back({d,k});
k++;
r[k]=0;
a[d].push_back({i,k});
k++;
}
for(i=n+1;i<=n+m;i++)
{
r[k]=1;
a[s].push_back({i,k});
k++;
r[k]=0;
a[i].push_back({s,k});
k++;
}
n=n+m+2;
flux_maxim();
if(sol!=m)
g<<0;
else
{
for(j=nn+1;j<=nn+m;j++)
{
l=a[j].size();
for(i=0;i<l;i++)
if(r[a[j][i].poz]==0)
{
g<<a[j][i].x<<'\n';
break;
}
}
}
}
};
class Cartile{
private:
int z[202][202],b[202][202],sol[212],pp[212],viz[212];
struct elem
{
int x,muchie;
};
vector<elem>a[212];
pair<int,int>w[212],q[40002];
stack<int>stk;
struct vulpe
{
int x,y,r;
};
vulpe v[52];
public:
void solution()
{
ifstream f("cartite.in");
ofstream g("cartite.out");
int p,n,m,xc,yc,nrv,nrg,x1,y1,x2,y2,i,k=0,st=1,dr=0,x,y,l;
f>>p>>n>>m>>xc>>yc>>nrv;
for(i=1;i<=nrv;i++)
f>>v[i].x>>v[i].y>>v[i].r;
f>>nrg;
for(i=1;i<=nrg;i++)
{
f>>x1>>y1>>x2>>y2;
if(z[x1][y1]==0)
z[x1][y1]=++k,w[k]={x1,y1},b[x1][y1]=-2;
if(z[x2][y2]==0)
z[x2][y2]=++k,w[k]={x2,y2},b[x2][y2]=-2;
a[z[x1][y1]].push_back({z[x2][y2],i});
a[z[x2][y2]].push_back({z[x1][y1],i});
}
for(i=0;i<=n+1;i++)
b[i][0]=b[i][m+1]=-1;
for(i=0;i<=m+1;i++)
b[0][i]=b[n+1][i]=-1;
for(i=1;i<=nrv;i++)
{
b[v[i].x][v[i].y]=-1;
if(v[i].r!=0)
b[v[i].x+1][v[i].y]=b[v[i].x-1][v[i].y]=b[v[i].x][v[i].y+1]=b[v[i].x][v[i].y-1]=-1;
if(v[i].r==2)
{
if(v[i].x-2>=1)
b[v[i].x-2][v[i].y]=-1;
b[v[i].x-1][v[i].y+1]=-1;
if(v[i].y+2<=m)
b[v[i].x][v[i].y+2]=-1;
b[v[i].x+1][v[i].y+1]=-1;
if(v[i].x+2<=n)
b[v[i].x+2][v[i].y]=-1;
b[v[i].x+1][v[i].y-1]=-1;
if(v[i].y-2>=1)
b[v[i].x][v[i].y-2]=-1;
b[v[i].x-1][v[i].y-1]=-1;
}
}
if(b[xc][yc]!=-2)
q[++dr]={xc,yc};
b[xc][yc]=1;
x=xc;
y=yc;
while(st<=dr)
{
x=q[st].first;
y=q[st].second;
st++;
if(b[x+1][y]==0||b[x+1][y]==-2)
{
if(b[x+1][y]==-2)
{
b[x+1][y]=b[x][y]+1;
x++;
break;
}
else
{
b[x+1][y]=b[x][y]+1;
q[++dr]={x+1,y};
}
}
if(b[x-1][y]==0||b[x-1][y]==-2)
{
if(b[x-1][y]==-2)
{
b[x-1][y]=b[x][y]+1;
x--;
break;
}
else
{
b[x-1][y]=b[x][y]+1;
q[++dr]={x-1,y};
}
}
if(b[x][y+1]==0||b[x][y+1]==-2)
{
if(b[x][y+1]==-2)
{
b[x][y+1]=b[x][y]+1;
y++;
break;
}
else
{
b[x][y+1]=b[x][y]+1;
q[++dr]={x,y+1};
}
}
if(b[x][y-1]==0||b[x][y-1]==-2)
{
if(b[x][y-1]==-2)
{
b[x][y-1]=b[x][y]+1;
y--;
break;
}
else
{
b[x][y-1]=b[x][y]+1;
q[++dr]={x,y-1};
}
}
}
if(p==1)
{
g<<x<<" "<<y<<" "<<b[x][y]-1;
}
stk.push(z[x][y]);
k=0;
while(!stk.empty())
{
x=stk.top();
l=a[x].size();
if(pp[x]<l)
{
if(viz[a[x][pp[x]].muchie]==0)
stk.push(a[x][pp[x]].x),viz[a[x][pp[x]].muchie]=1;
pp[x]++;
}
else
{
sol[++k]=x;
stk.pop();
}
}
if(p==2)
{
for(i=k;i>=1;i--)
g<<w[sol[i]].first<<" "<<w[sol[i]].second<<'\n';
}
}
};
class Segmente{
private:
struct elem
{
double x,y;
};
elem v[36];
double dp[66002][36],d[36][36];
double dist(double x1,double y1,double x2,double y2)
{
return sqrtl((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
public:
void solution()
{
ifstream f("seg.in");
ofstream g("seg.out");
int t,n,i,l,j,p,stare;
double sol;
f>>t;
for(l=1;l<=t;l++)
{
f>>n;
for(i=1;i<=2*n;i++)
f>>v[i].x>>v[i].y;
for(i=1;i<=2*n;i++)
for(j=1;j<=2*n;j++)
d[i][j]=dist(v[i].x,v[i].y,v[j].x,v[j].y);
p=1;
for(i=1;i<=n-1;i++)
p*=2;
p--;
for(i=0;i<=p;i++)
for(j=1;j<=2*n;j++)
dp[i][j]=INF;
for(i=2;i<=n;i++)
dp[1<<(i-2)][2*i]=d[1][2*i-1],dp[1<<(i-2)][2*i-1]=d[1][2*i];
for(stare=1;stare<p;stare++)
for(i=2;i<=n;i++)
if((stare&(1<<(i-2)))!=0)
for(j=2;j<=n;j++)
if((stare&(1<<(j-2)))==0)
{
dp[stare|(1<<(j-2))][2*j]=min(dp[stare|(1<<(j-2))][2*j],dp[stare][2*i]+d[2*i][2*j-1]);
dp[stare|(1<<(j-2))][2*j-1]=min(dp[stare|(1<<(j-2))][2*j-1],dp[stare][2*i]+d[2*i][2*j]);
dp[stare|(1<<(j-2))][2*j]=min(dp[stare|(1<<(j-2))][2*j],dp[stare][2*i-1]+d[2*i-1][2*j-1]);
dp[stare|(1<<(j-2))][2*j-1]=min(dp[stare|(1<<(j-2))][2*j-1],dp[stare][2*i-1]+d[2*i-1][2*j]);
}
sol=INF;
for(i=3;i<=2*n;i++)
sol=min(sol,dp[p][i]+d[i][2]);
if(n==1)
sol=0;
g<<fixed<<setprecision(6)<<sol<<'\n';
}
}
};
class TaramulNicaieri{
private:
vector<int>a[205];
int n,s,d,sol,r[205][205],tata[205],in[205],out[205];
bool viz[205];
queue<int>q;
public:
inline bool bfs()
{
int i,x,l;
for(i=1;i<=n;i++)
viz[i]=0,tata[i]=0;
q.push(s);
viz[s]=1;
while(!q.empty())
{
x=q.front();
q.pop();
l=a[x].size();
for(i=0;i<l;i++)
if(viz[a[x][i]]==0&&r[x][a[x][i]]>0)
{
viz[a[x][i]]=1;
tata[a[x][i]]=x;
q.push(a[x][i]);
}
}
return viz[d];
}
inline void flux_maxim()
{
int i,j,flow,l=a[d].size();
while(bfs()!=0)
{
for(i=0;i<l;i++)
if(tata[a[d][i]]!=0&&r[a[d][i]][d]>0)
{
flow=r[a[d][i]][d];
for(j=a[d][i];j!=s;j=tata[j])
{
flow=min(flow,r[tata[j]][j]);
if(flow==0)
break;
}
if(flow!=0)
{
r[a[d][i]][d]-=flow;
r[d][a[d][i]]+=flow;
for(j=a[d][i];j!=s;j=tata[j])
{
r[tata[j]][j]-=flow;
r[j][tata[j]]+=flow;
}
sol+=flow;
}
}
}
}
void solution()
{
ifstream f("harta.in");
ofstream g("harta.out");
int i,sum=0,j,l,nn;
f>>n;
nn=n;
for(i=1;i<=n;i++)
{
f>>out[i]>>in[i];
sum+=in[i];
}
s=2*n+1;
d=2*n+2;
for(i=1;i<=n;i++)
{
a[s].push_back(i);
a[i].push_back(s);
a[i+n].push_back(d);
a[d].push_back(i+n);
r[s][i]=out[i];
r[i+n][d]=in[i];
for(j=1;j<=n;j++)
if(i!=j)
{
a[i].push_back(j+n);
a[j+n].push_back(i);
r[i][j+n]=1;
}
}
n=n*2+2;
flux_maxim();;
g<<sum<<'\n';
for(i=1;i<=nn;i++)
{
l=a[i].size();
for(j=0;j<l;j++)
if(a[i][j]<=2*nn&&r[i][a[i][j]]==0)
g<<i<<" "<<a[i][j]-nn<<'\n';
}
}
};
int main()
{
// Negot n;
// n.solution();
// Cc c;
// c.solution();
// Senat s;
// s.solution();
// Cartile c;
// c.solution();
// Segmente s;
// s.solution();
TaramulNicaieri t;
t.solution();
return 0;
}