#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> a;
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;
vector<bitset<MAXN>> b(n);
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
a[u][v] = A[u][v];
b[u][v] = a[u][v];
}
b[u][u] = 1;
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++)
dist[u][v] = (a[u][v]) ? 1 : INF;
dist[u][u] = 0;
}
vector<bool> removed(n);
queue<int> q;
for (int u = 0; u < n; u++) q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
if (removed[u]) continue;
for (int v = 0; v < n; v++) {
if (u == v) continue;
if ((b[u] & b[v]) == b[u] && a[u][v]) {
removed[u] = true;
for (int w = 0; w < n; w++) if (a[u][w]) {
b[u][w] = b[w][u] = 0;
q.push(w);
}
break;
}
}
}
if (accumulate(removed.begin(), removed.end(), 0) < n - 1)
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 (a[p][u]) {
mn = u;
break;
}
for (int u = mn + 1; u < n; u++) {
if (a[p][u] && dist[u][r] < dist[mn][r]) mn = u;
}
p = mn;
return mn;
}
