#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define F first
#define S second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pq priority_queue
#include "game.h"
using namespace std;
constexpr int debug = 1;
constexpr int N = 1507;
//queue<int> possible_tree[N];
int possible_connect[N];
bool no_edge[N][N];
bool istree[N];
int vertices;
bool first = 1;
void initialize(int n){
vertices = n;
}
void add_tree(int s){
istree[s] = 1;
for(int i = 0; i < vertices; i++){
if((!istree[i]) && (!no_edge[i][s])){
//possible_tree[i].push(s);
possible_connect[i]++;
}
}
}
int hasEdge(int u, int v){
if(istree[u] && istree[v]) return 1;
else if(first){
first = 0;
add_tree(u);
add_tree(v);
return 1;
}
else if(istree[u] || istree[v]){
if(istree[u]) swap(v,u);
if(possible_connect[u] == 1){
add_tree(u);
return 1;
}
else{
possible_connect[u]--;
}
}
no_edge[u][v] = no_edge[v][u] = 1;
return 0;
}
