#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 500;
constexpr int INF = 1e6;
int n;
int p = 0;
array<array<bool, MAXN>, MAXN> areal;
auto dist = []() constexpr {
array<array<int, MAXN>, MAXN> dist;
for (auto& a : dist)
a.fill(INF);
return dist;
}();
int start(int N, bool a[MAXN][MAXN]) {
n = N;
for (int u = 0; u < n; u++)
for (int v = 0; v < n; v++)
areal[u][v] = a[u][v];
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++)
dist[u][v] = (areal[u][v]) ? 1 : INF;
dist[u][u] = 0;
}
array<int, MAXN> deg{};
for (int u = 0; u < n; u++)
for (int v = 0; v < n; v++)
deg[u] += a[u][v];
queue<int> q;
for (int u = 0; u < n; u++)
if (deg[u] == 1) q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) {
if (!a[u][v]) continue;
deg[v]--;
if (deg[v] == 1) q.push(v);
a[u][v] = false;
a[v][u] = false;
}
}
for (int u = 0; u < n; u++)
for (int v = u + 1; v < n; v++)
for (int w = v + 1; w < n; w++)
if (a[u][v] && a[v][w] && a[w][u])
a[u][v] = a[v][u] = a[v][w] = a[w][v] = a[w][u] = a[u][w] = false;
array<array<int, MAXN>, MAXN> C4;
for (auto& v : C4)
v.fill(-1);
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (!a[u][v]) continue;
for (int w = v + 1; w < n; w++) {
if (!a[u][w]) continue;
int x = C4[v][w];
if (x != -1)
a[x][v] = a[v][x] = a[x][w] = a[w][x] = a[u][v] = a[v][u] = a[u][w] = a[w][u] = false;
C4[v][w] = u;
}
}
}
for (int u = 0; u < n; u++)
for (int v = u + 1; v < n; v++)
if (a[u][v])
return -1;
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
for (int w = 0; w < n; w++) {
if (dist[v][u] != INF && dist[u][w] != INF)
dist[v][w] = min(dist[v][w], dist[v][u] + dist[u][w]);
}
}
}
return p = 0;
}
int nextMove(int r) {
if (dist[p][r] <= 1) return p = r;
if (dist[p][r] == 2) return p;
int mn = -1;
for (int u = 0; u < n; u++) if (areal[p][u]) {
mn = u;
break;
}
for (int u = mn + 1; u < n; u++) {
if (areal[p][u] && dist[u][r] < dist[mn][r]) mn = u;
}
p = mn;
return mn;
}
