#include<bits/stdc++.h>
#include "coprobber.h"
using namespace std;
const int MAXN = 510;
vector <int> g[MAXN];
vector <pair <int, int>> backedges;
int pai[MAXN];
int h[MAXN];
int dist[MAXN][MAXN];
int at;
void dfs(int v, int p){
pai[v] = p;
for(auto x : g[v]){
if(x == p) continue;
if(pai[x] != -1){
backedges.push_back({x, v});
continue;
}
h[x] = h[v]+1;
dfs(x, v);
}
return;
}
int start(int n, bool a[MAX_N][MAX_N]){
memset(pai, -1, sizeof pai);
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(a[i][j])
g[i].push_back(j);
}
}
dfs(1, 1);
for(auto [a, b] : backedges){
if(h[a] > h[b]) swap(a, b);
int con = 2;
while(b != a){
if(pai[b] == a) break;
if(con > 4) break;
set <int> s;
int t = b;
while(t != a){
s.insert(t);
t = pai[t];
}
s.insert(a);
int minalt = 1e9, ver = -1;
for(auto x : g[b]){
if(s.find(x) == s.end()) continue;
if(x == a) continue;
if(minalt > h[x]){
ver = x;
minalt = min(minalt, h[x]);
}
}
con++;
b = ver;
}
if(con > 4){
return -1;
}
}
memset(dist, -1, sizeof dist);
for(int i = 0;i < n;i++){
dist[i][i] = 0;
queue <int> q;
q.push(i);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto x : g[v]){
if(dist[i][x] != -1) continue;
dist[i][x] = dist[i][v]+1;
q.push(x);
}
}
}
return at = 0;
}
int cover[MAXN];
int nextMove(int r){
//cout << dist[at][r] << ' ';
if(dist[at][r] == 0){
return at;
}
if(dist[at][r] == 1){
return at = r;
}
if(dist[at][r] == 2){
return at = at;
}
if(dist[at][r] == 3){
int v = at;
for(auto x : g[r]){
for(auto y : g[x]){
cover[y]++;
}
}
int ver = g[v][0], mindist = dist[v][ver], mincover = cover[ver];
for(auto x : g[v]){
if(mindist > dist[v][x]){
ver = x;
mindist = dist[v][ver];
mincover = cover[x];
}
else if(mincover > cover[x]){
ver = x;
mindist = dist[v][ver];
mincover = cover[x];
}
}
for(auto x : g[r]){
for(auto y : g[x]){
cover[y]++;
}
}
return at = ver;
}
int v = at;
int ver = g[v][0], mindist = dist[v][ver], mincover = cover[ver];
for(auto x : g[v]){
if(mindist > dist[v][x]){
ver = x;
mindist = dist[v][ver];
mincover = cover[x];
}
else if(mincover > cover[x]){
ver = x;
mindist = dist[v][ver];
mincover = cover[x];
}
}
return at = ver;
}
