#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
const int maxn = 510;
struct State
{
int u, w, q;
};
int n;
int win[maxn][maxn][2];
int mark[maxn][maxn][2];
vector<int> grafo[maxn];
vector<State> game[maxn][maxn][2];
void build(int u, int w, int q)
{
if (u == w) return;
if (q == 0)
{
game[u][w][0].push_back({u, w, 1});
for (auto v: grafo[u])
game[u][w][0].push_back({v, w, 1});
}
else
{
for (auto v: grafo[w])
game[u][w][1].push_back({u, v, 0});
}
}
void dfs(int u, int w, int q)
{
if (mark[u][w][q] == 2) return;
if (u == w)
{
if (q == 0) win[u][w][q] = 1;
else win[u][w][q] = 0;
mark[u][w][q] = 2;
return;
}
mark[u][w][q] = 1;
for (auto S: game[u][w][q])
{
if (q == 0)
{
int v = S.u;
if (mark[v][w][1])
{
if (mark[v][w][1] == 2 && win[v][w][1] == 0) win[u][w][0] = 1;
continue;
}
dfs(v, w, 1);
if (win[v][w][1] == 0) win[u][w][0] = 1;
}
else
{
int v = S.w;
if (mark[u][v][0])
{
if (mark[u][v][0] == 1 || win[u][v][0] == 0) win[u][w][1] = 1;
continue;
}
dfs(u, v, 0);
if (win[u][v][0] == 0) win[u][w][1] = 1;
}
}
mark[u][w][q] = 2;
}
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (A[i][j])
grafo[i].push_back(j);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int q = 0; q < 2; q++)
build(i, j, q);
for (int i = 0; i < 1; i++)
{
memset(win, 0, sizeof win); memset(mark, 0, sizeof mark);
for (int j = 0; j < n; j++)
dfs(i, j, 0);
bool ok = 1;
for (int j = 0; j < n; j++)
if (win[i][j][0] == 0)
ok = 0;
if (ok) return i;
}
return -1;
}
int nextMove(int R)
{
return 0;
}
