#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> adj;
vector<bool> vis;
vector<bool> is_three;
bool has_cycle(int u, int p = -1, int gp = -1, int ggp = -1) {
// Special handle cycle of length 3
if (ggp != -1 && u == ggp) {
is_three[u] = 1;
is_three[p] = 1;
is_three[gp] = 1;
vis[u] = true;
return false;
}
if (is_three[u])
return false;
if (vis[u]) {
return true;
}
vis[u] = true;
for (int v : adj[u])
if (v != p)
if (has_cycle(v, u, p, gp))
return true;
return false;
}
vector<int> tin, tout, par;
int tick = 0;
void et(int u, int p = -1) {
if (vis[u])
return;
vis[u] = 1;
tin[u] = tick++;
par[u] = p;
for (int v : adj[u])
if (v != p)
et(v, u);
tout[u] = tick++;
}
bool subt(int u, int p) { return tin[p] <= tin[u] && tout[u] <= tout[p]; }
int cop = 0;
int start(int N, bool A[MAX_N][MAX_N]) {
n = N;
adj.resize(n);
for (int u = 0; u < N; u++)
for (int v = 0; v < N; v++)
if (A[u][v])
adj[u].push_back(v);
is_three.resize(n);
vis.resize(n);
if (has_cycle(0))
return -1;
tin.resize(n);
tout.resize(n);
par.resize(n);
fill(vis.begin(), vis.end(), false);
et(0);
return 0;
}
int nextMove(int R) {
if (R == cop)
return cop;
for (int v : adj[cop])
if (v != par[cop] && (v == R || subt(R, v))) {
cop = v;
return cop;
}
cop = par[cop];
return cop;
}
