#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int NN = 500;
bool a[NN][NN];
int n, cur, par = -1;
vector <int> v[NN];
int start(int N, bool a[NN][NN]) {
n = N;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j]) {
v[i].pb (j);
v[j].pb (i);
}
}
}
return 0;
}
int icindemi (int x, int par, int y) {
int ret = 0;
if (x == y) return 1;
for (int i : v[x]) {
if (i == par) continue;
ret |= icindemi (i, x, y);
}
return ret;
}
int nextMove(int R) {
for (int i : v[cur]) {
if (icindemi(i, -1, R)) {
cur = i;
break;
}
}
return cur;
}
/*
static const bool TRACK_CALLS = false;
static int N, CopCanWin;
static bool A[NN][NN];
// Where should the robber go if the first index is the cop's
// position and the second index is the robber's position?
// RS[c][N] stores robber's starting corners.
static int RobberStrategy[NN][NN + 1];
// Visited positions are stored in the following array
static bool VisitedPositions[NN][NN];
static const int OK = 0, PARTFAIL = 1, FAIL = 2;
static const char* Messages[] = { "OK", "PARTFAIL", "FAIL" };
typedef pair<int, const char*> GraderResult;
static GraderResult runGrader() {
int copCorner = start(N, A);
if (TRACK_CALLS)
fprintf(stderr, "start() = %d\n", copCorner);
if ((copCorner != -1) && !CopCanWin)
return GraderResult(FAIL, "Cop cannot catch the robber, but start() did not return -1");
if ((copCorner == -1) && CopCanWin)
return GraderResult(FAIL, "Cop can catch the robber, but start() returned -1");
if (!CopCanWin)
return GraderResult(OK, NULL);
if (copCorner < 0 || copCorner >= N)
return GraderResult(FAIL, "start() returned a value that is outside the 0..N-1 range");
int robberCorner = RobberStrategy[copCorner][N];
if (robberCorner == copCorner) // If N = 1
return GraderResult(OK, NULL);
while (true) {
int nextCopCorner = nextMove(robberCorner);
if (TRACK_CALLS)
fprintf(stderr, "nextMove(%d) = %d\n", robberCorner, nextCopCorner);
/**
* Check if the move is valid:
* - the returned corner is within bounds
* - the new corner is either the same or is a neighbour to the old one
*/
/*
if (nextCopCorner < 0 || nextCopCorner >= N
|| !(copCorner == nextCopCorner || A[copCorner][nextCopCorner]))
return GraderResult(PARTFAIL,
"nextMove() returned a value that is either outside 0..N-1 "
"or the new cop position is not a neighbour to the previous one");
copCorner = nextCopCorner;
// Check if the same position has not been encountered before
if (VisitedPositions[copCorner][robberCorner])
return GraderResult(PARTFAIL, "the situation repeated");
VisitedPositions[copCorner][robberCorner] = true;
// Check the winning condition
if (copCorner == robberCorner)
return GraderResult(OK, NULL);
robberCorner = RobberStrategy[copCorner][robberCorner];
// Moving to cop's position could have been the only
// valid move for the robber
if (copCorner == robberCorner)
return GraderResult(OK, NULL);
}
}
int main() {
freopen ("input.txt", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int t;
scanf("%d", &t);
A[i][j] = t;
}
scanf("%d", &CopCanWin);
if (CopCanWin) {
for (int c = 0; c < N; c++)
for (int r = 0; r <= N; r++)
scanf("%d", &RobberStrategy[c][r]);
}
GraderResult result = runGrader();
puts(Messages[result.first]);
if (result.second != NULL)
puts(result.second);
return 0;
}
///*
4
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
1
0 0 0 0 1
2 0 0 0 2
1 0 0 0 1
1 0 0 0 1
*/
