// credit: bieoiibe
#include "coprobber.h"
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
#define vektor vector
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll Mod = 1e9 + 7;
vector <vector <int>> f(500, vector <int>(500, 10000));
vector <vector <int>> graph(500);
vektor <int> v(500, 0);
int start(int n, bool a[500][500]){
for(int i = 0 ; i < n; i ++){
for(int j = i; j < n; j ++){
if(a[i][j]) {
graph[i].pb(j);
graph[j].pb(i);
}
}
}
for(int i = 0; i < n; i ++){
f[i][i] = 0;
for(auto& x : graph[i]) f[i][x] = f[x][i] = 1;
}
for(int j = 0; j < n; j ++){
for(int i = n - 1; i >= 0; i --){
for(int k = 0; k < n; k ++){
if(f[i][j] + f[j][k] < f[i][k]) f[i][k] = f[i][j] + f[j][k];
}
}
}
// for(int i = 0; i < n; i ++)
// for(int j = 0; j < n; j ++)
// cout << i << " " << j << " " << f[i][j] << "\n";
int mn = INT_MAX;
for(int i = 0; i < n; i ++){
queue <int> q;
vector <int> root(n, 0), val(n, -1);
q.push(i);
val[i] = 0;
while(!q.empty()){
int s = q.front();
q.pop();
for(auto& x : graph[s]){
if(val[x] >= 0 && root[x] != root[root[s]] && val[x] + val[s] >= 2){
mn = min(mn, val[x] + val[s] + 1);
break;
}
if(val[x] == -1){
val[x] = val[s] + 1;
root[x] = s;
q.push(x);
}
}
}
}
v[0] = 1;
if(mn > 5) return -1;
return 0;
}
int cur = 0, val = 10000;
int nextMove(int pos){
int temp = cur;
for(auto& x : graph[temp]){
if(f[x][pos] < val && f[x][pos] && !v[x]){
cur = x;
val = f[x][pos];
}
}
v[cur] = 1;
return cur;
}
void solve(){
int n;
cin >> n;
bool a[500][500];
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++) cin >> a[i][j];
}
cout << start(n, a) << "\n";
int s;
while(cin >> s){
cout << nextMove(s) << "\n";
}
}
// signed main()
// {
// cin.tie(0)->sync_with_stdio(0);
// // if(fopen("blank.inp", "r")){
// // freopen("blank.inp", "r", stdin);
// // freopen("blank.out", "w", stdout);
// // }
// // // cout << 1; return 0;
// ll n = 1;
// // // cin >> n;
// // while(n) {
// // solve();
// // n --;
// // cout << "\n";
// // }
// // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
// }
