#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const int MAXN=5e2+10;
typedef pair<int,int> pii;
int n,cnt[MAXN][MAXN][2],updt[MAXN][MAXN],atual;
vector<int> g[MAXN];
bool z[MAXN][MAXN][2];
void propag(int u,int x,int p){
if(p==1){
for(auto j:g[x]){
if(z[u][j][0]==1) continue;
cnt[u][j][0]--;
if(!cnt[u][j][0]){
z[u][j][0]=1;
propag(u,j,0);
}
}
}
else{
if(!z[u][x][1]){
z[u][x][1]=1;
updt[u][x]=u;
propag(u,x,1);
}
for(auto j:g[u]){
if(z[j][x][1]) continue;
z[j][x][1]=1;
updt[j][x]=u;
propag(j,x,1);
}
}
}
int start(int N, bool A[MAX_N][MAX_N]){
n=N;
fall(i,0,n-1)
fall(j,0,n-1) if(A[i][j]) g[i].pb(j);
fall(i,0,n-1){
fall(j,0,n-1) cnt[i][j][0]=sz(g[j]);
}
fall(i,0,n-1){
if(z[i][i][1]) continue;
z[i][i][1]=1;
propag(i,i,1);
}
fall(i,0,n-1){
if(z[i][i][0]) continue;
z[i][i][0]=1;
propag(i,i,0);
}
fall(i,0,n-1){
bool ok=1;
fall(j,0,n-1) ok&=(z[i][j][1]);
atual=i;
if(ok) return i;
}
return -1;
}
int nextMove(int R){
if(R==atual) return atual;
return atual=updt[atual][R];
}
