Time Limit: 1000MS | Memory Limit: 10000K | |||
Total Submissions: 4097 | Accepted: 1499 | Special Judge |
Description
A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists.
Example
Consider the following target:
Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct.
Write a program that: verifies whether any correct volley of hits exists and if so, finds one of them.
Input
The first line of each block contains two integers r and c separated by a single space, 2 <= r <= c <= 1000. These are the numbers of rows and columns, respectively. Each of the next c lines in the block contains two integers separated by a single space. The integers in the input line i + 1 in the block, 1 <= i <= c, are labels of rows with white squares in the i-th column.
Output
Sample Input
2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
Sample Output
2 3 1 4
NO
Source
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std; #define N 1005
#define inf 999999999 int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int abs(int x,int y){return x<?-x:x;} int from[N];
int to[N];
bool visited[N];
int n, m;
vector<int>ve[N]; int march(int u){
int i, v;
for(i=;i<ve[u].size();i++){
v=ve[u][i];
if(!visited[v]){
visited[v]=true;
if(from[v]==-||march(from[v])){
from[v]=u;
to[u]=v;
return ;
}
}
}
return ;
} main()
{
int t, i, j, k, u, v;
cin>>t;
while(t--){
scanf("%d %d",&n,&m);
for(i=;i<=m;i++) ve[i].clear();
for(i=;i<=m;i++){
scanf("%d %d",&u,&v);
ve[i].push_back(u);
ve[i].push_back(v);
}
if(n>m) {
printf("NO\n");continue;
}
memset(from,-,sizeof(from));
int num=;
for(i=;i<=m;i++){
memset(visited,false,sizeof(visited));
march(i);
}
int f=;
for(i=;i<=n;i++){
if(from[i]==-){
f=;break;
}
}
if(!f){
printf("NO\n");continue;
}
for(i=;i<=m;i++){
if(!to[i]){
to[i]=ve[i][];
}
}
printf("%d",to[]);
for(i=;i<=m;i++) printf(" %d",to[i]);
cout<<endl;
}
}