Police Catching the Thief

This is an interactive problem. A single policeman and a thief are on a connected undirected graph with N vertices (numbered from 0 to N−1). The edges represent the alleys between street corners. At the beginning, the policeman chooses a starting vertex by calling the function start(N, A) while the thief chooses an initial vertex arbitrarily. In each round, the policeman moves first – he may either stay at his current vertex or move to an adjacent vertex. Then the thief moves – but the thief is not allowed to remain at the same vertex, and must move to one of its adjacent vertices. Both players know the full graph and will play optimally. The policeman’s goal is to capture the thief (i.e. to be at the same vertex as the thief), while the thief will try to prolong capture as much as possible, and if possible, avoid capture forever.

The interactive protocol requires you to implement two functions:

int start(int N, bool A[MAX_N][MAX_N]);
int nextMove(int R);

Here, the function start is called exactly once at the beginning with:

• N – the number of vertices.
• A – an N×N boolean matrix in which A[i][j] is true if there is an alley connecting vertex i and vertex j (all alleys are two‐way and there are no self‐loops).

If the policeman can eventually capture the thief (assuming both play optimally – note that the thief is assumed to use the best evasion strategy), then start must return the policeman’s starting vertex (more precisely, the vertex at which the eventual capture will occur). Otherwise, if the thief can evade capture indefinitely, start should return -1.

After start is called (if it does not return -1), the function nextMove will be repeatedly called. In each round the argument R given to nextMove is the current vertex of the thief. The function nextMove should decide the policeman’s move for that round and return the policeman’s new vertex. The program must then terminate when one of the following happens:

• An illegal move is returned by nextMove.
• The thief can evade capture forever.
• The thief is captured (i.e. at some point the policeman and the thief meet at the same vertex).

Notes (in LaTeX):

Assume that the vertices are numbered from $0$ to $N-1$, and the connectivity is given by a symmetric matrix $A$ with $A[i,i]=\texttt{false}$ and for $i\neq j$, $A[i,j]=\texttt{true}$ if vertices $i$ and $j$ are adjacent.

Your solution should implement an optimal strategy for both sides. In particular, if the graph is cop-win (i.e. the policeman has a winning strategy even if the thief plays optimally), then your functions should simulate the minimax strategy yielding the minimum number of rounds until capture. Otherwise, if the graph is not cop‐win so that the thief can evade capture forever, you must output -1 in the start function.

inputFormat

The input is given as follows:

• The first line contains an integer N, the number of vertices.
• The next N lines each contain N integers (each 0 or 1) separated by spaces. The j-th number in the i-th line is 1 if there is an alley between vertex i and vertex j, and 0 otherwise.

You may assume that the graph is connected, undirected (so the matrix is symmetric) and has no self‐loops.

outputFormat

If the policeman can force a capture under optimal play (with the thief also playing optimally), the start function should output the policeman’s starting vertex (i.e. the vertex where capture will eventually occur) and the subsequent moves will be given by nextMove. Otherwise, if the thief can evade capture forever, start must return -1.

Note: In the offline test cases the interaction is simulated; your program should follow the interaction protocol exactly.

sample

3
0 1 0
1 0 1
0 1 0

0
1
0
...

</p>