#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1510;
int n;
int used[maxn], in_st[maxn * maxn], in_mst[maxn * maxn];
vector < int > st, mst;
void initialize(int N)
{
n = N;
for (int i = 0; i < n; i ++)
for (int j = i + 1; j < n; j ++)
{
if (i != j)
{
if (i + 1 == j)
mst.push_back(i * n + j), in_mst[i * n + j] = 1;
else
st.push_back(i * n + j), in_st[i * n + j] = 1;
}
}
}
vector < int > adj[maxn];
void dfs(int v, int cnt)
{
used[v] = cnt;
for (int u : adj[v])
{
if (!used[u])
dfs(u, cnt);
}
}
int hasEdge(int u, int v)
{
//cout << "----------------" << endl;
if (u > v)
swap(u, v);
int hs = u * n + v;
if (!in_mst[hs])
{
in_st[hs] = 0;
return 0;
}
for (int i = 0; i < n; i ++)
adj[i].clear(), used[i] = 0;
vector < int > new_st;
for (int cur: st)
{
if (in_st[cur])
new_st.push_back(cur);
}
st = new_st;
vector < int > new_mst;
for (int cur : mst)
{
if (in_mst[cur])
new_mst.push_back(cur);
}
mst = new_mst;
for (int edge : mst)
{
if (edge == hs)
continue;
///cout << edge / n << " " << edge % n << endl;
adj[edge / n].push_back(edge % n);
adj[edge % n].push_back(edge / n);
}
dfs(0, 1);
for (int i = 0; i < n; i ++)
if (used[i] == 0)
{
dfs(i, 2);
break;
}
for (int edge : st)
{
if (edge == hs)
continue;
if (used[edge / n] != used[edge % n])
{
///cout << "replace " << edge / n << " " << edge % n << endl;
in_st[hs] = 0;
in_mst[edge] = 1;
mst.push_back(edge);
in_mst[hs] = 0;
in_st[edge] = 0;
/**st.erase(hs);
mst.insert(edge);
st.erase(edge);
mst.erase(hs);*/
return 0;
}
}
return 1;
}
