#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 21;
int N; int dsu[MAXN];
int e[MAXN][MAXN];
void initialize(int n){
memset(e, -1, sizeof(e)); N = n;
for (int i = 0; i < n; ++i) dsu[i] = i;
}
int parent(int x){
return dsu[x] == x ? x : dsu[x] = parent(dsu[x]);
}
void merge(int x, int y){
dsu[x] = parent(x);
dsu[y] = parent(y);
if (dsu[x] != dsu[y]) dsu[y] = x;
}
//exist bad partition
bool bad(int X){
vector<int> a, b;
for (int i = 0; i < N; ++i){
if (parent(i) == X) a.pb(i);
else b.pb(i);
}
bool B = 1;
for (int x: a)
for (int y: b)
if (e[x][y] != 0) B = 0;
return B;
}
int hasEdge(int x, int y){
e[x][y] = 0, e[y][x] = 0;
if (bad(parent(x)) || bad(parent(y))){
e[x][y] = 1, e[y][x] = 1;
merge(x, y);
}
//cout << x << ' ' << y << " -> " << e[x][y] << endl;
return e[x][y];
}
/*int main(){
initialize(4);
hasEdge(0, 3);
hasEdge(1, 0);
hasEdge(0, 2);
hasEdge(3, 1);
hasEdge(1, 2);
hasEdge(2, 3);
}*/
