#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int n = 4, m = n * (n - 1) / 2;
typedef array<int,m> state;
state tmp;
map<state,int> mp[m];
pair<int,int> edge[m];
int par[n];
int findpar(int x)
{
return par[x] != -1 ? par[x] = findpar(par[x]) : x;
}
bool unite(int u, int v)
{
u = findpar(u);
v = findpar(v);
if (u != v) return par[u] = v, true;
return false;
}
bool check(const state &st)
{
memset(par, -1, sizeof par);
int cnt = 0;
for (int i = 0; i < m; i++) {
if (st[i]) cnt += unite(edge[i].first, edge[i].second);
}
return cnt == n - 1;
}
int call(state st, int count)
{
if (mp[count].count(st)) return mp[count][st];
int &d = mp[count][st] = 2;
if (count == m - 1) {
for (int i = 0; i < m; i++) {
if (st[i] == 2) {
state tmp1 = st;
state tmp2 = st;
tmp1[i] = 0;
tmp2[i] = 1;
if (check(tmp1) == check(tmp2)) {
return d = 1;
}
}
}
return d = 2;
}
for (int i = 0; i < m; i++) {
if (st[i] == 2) {
state tmp1 = st;
state tmp2 = st;
tmp1[i] = 0;
tmp2[i] = 1;
if (call(tmp1, count + 1) != 2 && call(tmp2, count + 1) != 2) {
return d = 1;
}
}
}
return d;
}
void initialize(int n)
{
assert(::n == n);
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edge[cnt++] = {i, j};
}
}
for (int i = 0; i < m; i++) tmp[i] = 2;
assert(call(tmp, 0) == 2);
}
int cnt = 0;
int hasEdge(int u, int v)
{
if (u > v) swap(u, v);
int id = 0;
while (edge[id] != make_pair(u, v)) id++;
if (tmp[id] != 2) return tmp[id];
cnt++;
if (cnt == m) return 0;
tmp[id] = 0;
if (call(tmp, cnt) == 2) return 0;
tmp[id] = 1;
return 1;
}
