#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n;
vector<int> cnt, adj1, adj2, val;
int aux = 0;
void initialize(int N) {
n = N;
cnt = vector<int>(n, 0);
adj1 = adj2 = vector<int>(n);
val = vector<int>(n, -1);
}
int hasEdge(int u, int v) {
if (val[u] == -1) {
val[u] = aux;
++aux;
}
if (val[v] == -1) {
val[v] = aux;
++aux;
}
if (cnt[val[u]]+cnt[val[v]] == 0) {
++cnt[val[u]]; ++cnt[val[v]];
adj1[max(val[u], val[v])] = min(val[u], val[v]);
adj2[min(val[u], val[v])] = max(val[u], val[v]);
return 1;
}
if ((adj1[val[u]] != -1 && cnt[val[u]]+cnt[adj1[val[u]]] == 2*(n-1)-1) || (adj1[val[v]] != -1 && cnt[val[v]]+cnt[adj1[val[v]]] == 2*(n-1)-1) || (adj2[val[u]] != -1 && cnt[val[u]]+cnt[adj2[val[u]]] == 2*(n-1)-1) || (adj2[val[v]] != -1 && cnt[val[v]]+cnt[adj2[val[v]]] == 2*(n-1)-1)) {
++cnt[val[u]]; ++cnt[val[v]];
adj1[max(val[u], val[v])] = min(val[u], val[v]);
adj2[min(val[u], val[v])] = max(val[u], val[v]);
return 1;
}
++cnt[val[u]]; ++cnt[val[v]];
return 0;
}
