题目大意：
有一个R*C（R<=C）的棋盘，由黑白两色格子组成，每列只有两个白色格子，其余为黑色。
现在求：在每列恰巧取一个，每行最少取一个的取法，按列的顺序由小到大输出取出棋子所在的行。
我的思路：
由于每行最少取一个，可以先把行的最大二分图匹配做出来，如果行都不能满足，肯定是无解的。
若行能匹配，再在流图中找到匹配的路径。
那么所有的行都找到了相应的列。那么余下的列随便匹配就好了。
网上思路：
用带上下限的网络流来做，基本上做到这种专题了。但是想到了不需要用这种方法也能过。
先讲讲这种上下限吧：
行至少有一个流，下限为1，上限INF。
列恰好取一次,下限为1，上限为1。
常用的二分图模型套入就好了。
接下来就是带上下限的网络流了.... 明天做吧。今天还不会建图....
#include<iostream>
#define MN 2222
#define MM 44444
#define INF 0x3FFFFFFF
#define FF(i,N) for( int i=0;i<N;i++ )
#define CC(a) memset(a,0,sizeof(a))
template<class T>inline void checkmin( T &a,T b ){ if(a>b||a==-1) a=b; }
using namespace std;int R,C,s,t,Si,Ti,alloc;
struct edge{int v,c,f,next;
}E[MM];int gap[MN],cur[MN],pre[MN],dis[MN],head[MN];
int Ni[MN],No[MN];
int rec[MN][2];
void addEdge( int u,int v,int c,int cc=0 )
{E[alloc].v=v; E[alloc].c=c;E[alloc].next=head[u]; head[u]=alloc++;E[alloc].v=u; E[alloc].c=cc;E[alloc].next=head[v]; head[v]=alloc++;
}void setG()
{CC(E),alloc=0;memset( head,-1,sizeof(head) );scanf( "%d%d",&R,&C );s=0;t=R+C+1;FF( i,R )addEdge( s,i+1,1 );FF( i,C ){scanf("%d %d",&rec[i+1][0],&rec[i+1][1] );addEdge( rec[i+1][0],i+1+R,1 );addEdge( rec[i+1][1],i+1+R,1 );}for( int i=1+R;i<=C+R;i++ )addEdge( i,t,1 );
}int sap()
{CC(gap),CC(dis);FF(i,t+1) cur[i]=head[i];int u=pre[s]=s,maxflow=0,aug=-1;gap[0]=t+1;while( dis[s]<=t ){
loop://printf( "hello\n" );for( int &i=cur[u];i!=-1;i=E[i].next ){int v=E[i].v;if( E[i].c-E[i].f&&dis[u]==dis[v]+1 ){pre[v]=u;checkmin( aug,E[i].c-E[i].f );u=v;if( v==t ){//printf("aug:%d",aug);maxflow+=aug;for( u=pre[u];v!=s;v=u,u=pre[u] )E[cur[u]].f+=aug,E[cur[u]^1].f-=aug;aug=-1;}goto loop;}}int mind=t;for( int i=head[u];i!=-1;i=E[i].next ){int v=E[i].v;if( E[i].c-E[i].f&&mind>dis[v] )cur[u]=i,mind=dis[v];}if( --gap[dis[u]]==0 )break;gap[dis[u]=mind+1]++;u=pre[u];}return maxflow;
}int main()
{int T;scanf("%d",&T);while( T-- ){setG();//printf("here!\n");int maxflow=sap();//printf( "%d\n",maxflow );if( maxflow!=R ){printf( "NO\n" );continue;}//sap();int find[MN];CC(find);for( int i=1+R;i<=C+R;i++ )for( int j=head[i];j!=-1;j=E[j].next )if( E[j^1].c==E[j^1].f&&E[j].v!=t ){find[i-R]=E[j].v;break;}for( int i=1;i<=C;i++ )if( find[i] ){if( i!=1 )printf( " " );printf( "%d",find[i] );}else{if( i!=1 )printf( " " );printf( "%d",rec[i][0] );}printf( "\n" );}return 0;
}