# POI 2 Stage 2 Board Covering ( Bipartite Matching )

http://main.edu.pl/en/archive/oi/2/sza

In the only line of the standard input there are written four numbers separated by single spaces. The first number is the dimension of the board n, and the three other are the numbers of the cut out squares. The last number is followed by the end of the line.

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int N, X, Y, Z;
vector< int > G[ MAXN * MAXN ];
int bf[ MAXN * MAXN ];

bool find_mate( int u, vector< int > &vis ){
for( int i = 0; i < G[ u ].size(); ++i ){
int v = G[ u ][ i ];
if( vis[ v ] ) continue;
vis[ v ] = 1;
if( bf[ v ] == -1 or find_mate( bf[ v ], vis ) ){
bf[ v ] = u;
return true;
}
}
return false;
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> X >> Y >> Z;
for( int i = 0; i < N; ++i ){
for( int j = 0; j < N; ++j ){
if( i + j & 1 ) continue;
int p = i * N + j + 1;
if( p == X or p == Y or p == Z ) continue;
for( int di = 0; di < 4; ++di ){
int ni = i + dx[ di ];
int nj = j + dy[ di ];
if( not ( 0 <= ni and ni < N and 0 <= nj and nj < N ) ) continue;
int np = ni * N + nj + 1;
if( np == X or np == Y or np == Z ) continue;
G[ i * N + j ].push_back( ni * N + nj );
}
}
}
{ // bipartite matching
int mcnt = 0;
memset( bf, -1, sizeof( bf ) );
for( int i = 0; i < N; ++i ){
for( int j = 0; j < N; ++j ){
if( i + j & 1 ) continue;
int p = i * N + j + 1;
if( p == X or p == Y or p == Z ) continue;
vector< int > vis( N * N );
if( not find_mate( i * N + j, vis ) ){
cout << "NIE\n";
exit( 0 );
}
++mcnt;
}
}
if( mcnt < ( N * N - 3 ) / 2 ){
cout << "NIE\n";
exit( 0 );
}
}
for( int i = 0; i < N; ++i ){
for( int j = 0; j < N; ++j ){
if( ~ ( i + j ) & 1 ) continue;
if( bf[ i * N + j ] == -1 ) continue;
cout << i * N + j + 1 << " " << bf[ i * N + j ] + 1 << "\n";
}
}
return 0;
}
```