题目描述

本题译自 BalticOI 2014 Day1 T1「Cop and Robber」

本题暂时只能支持 C++ / C++ 11 语言提交，需引入 coprobber.h 头文件方可正常评测。

Bytemore 的犯罪率又创历史新高。在所有的违法行为中，抢劫天天发生。然而当每次抢劫发生时，总是只有一个巡警孤身一人在街角的狭窄小巷之间追捕强盗。不幸的是，往往是强盗打赢这场追逐战，因为这些老奸巨猾的强盗早已对这个城市了如指掌。

Bytemore 市公安部门（英文缩写为 BCPD）正在组织一场最高会议来减少犯罪。其中一种可行的解决方案是在追捕盗贼时使用计算机远程协助警察。为此，BCPD 制作了一份精细的城市地图。现在他们需要一个大佬计算机程序来制定追捕策略。

警察追捕强盗的问题可以如下模式化：

• 这名警察会选择一个街角巡逻。
• 强盗会选择一个街角施行抢劫（他知道警察的位置）。从这时开始，我们总是假设警察与强盗互相知道对方的位置。
• 警察所可以进行的移动包括转移到另一个相邻的街角（即从一条小巷转移到另一条与之相连接的小巷）或等待（即不动）。
• 强盗所可以进行的移动同样包括转移到另一个相邻的街角。请注意，相比警察，强盗并不能等待，因为逃跑是他们的本能。
• 警察与强盗会一直轮流进行动作（从警察开始）直到以下一种情况发生：
  • 强盗能够一直躲避警察，使得强盗能够逃脱；
  • 他们其中任意一个作出移动之后在同一个街角相遇。在这种情况下，警察抓住了强盗。

你需要写一个程序，它对于给定的地图，能够确定警察是否有可能抓到强盗，且若果可以，输出警察抓到强盗时进行的移动数量。

你的程序须假设强盗总是做出最优方案。

---

交互函数原型

你需要写两个函数与交互器进行交互：

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

其中 start(N, A) 传入以下参数：

• N —— 街角的数量（街角以 0 到 N - 1 编号）；
• A —— 一个二维数组描述小巷：对于所有的 $0 \le i,j \le N-1$，若 $i$ 与 $j$ 不连通，则 A[i][j] = false，否则 A[i][j] = true。

所有小巷都是双向的（即对于所有 $i$ 和 $j$，A[i][j] = A[j][i]），并且不会出现自环（即对于所有 $i$，A[i][i] = false）。此外，你可以假设警察总能从其他街角通过小巷到达一个街角。

如果警察可能在由参数描述的地图上抓到强盗，函数 start 应该返回警察与强盗相遇的街角编号。否则返回 -1。

而 nextMove(R) 传入参数 R，表示当前强盗的所在的街角编号。该函数应返回这次移动之后警察所在的街角编号。

函数 start 必定会在第一次调用函数 nextMove 调用一次。如果 start 返回了 -1，那么 nextMove 将不会被调用。否则，nextMove 会被反复调用直到追捕行动结束。更确切地说，只要满足以下情况之一，程序必须终止：

• nextMove 返回了一个不合法的移动；
• 强盗能够一直躲避警察；
• 强盗被抓住了。

---

输入格式（交互器输入）

第一行，一个整数 $N$，表示街角的个数。
以下 $N$ 行，包含一个邻接矩阵 $A$。
其中每行包含 $N$ 个数字，要么是 0 要么是 1。

如果警察可以抓到强盗，下一行为 1，否则为 0。
如果上一行为 1，以下将会有 $N$ 行，描述强盗的策略。
每行 $N+1$ 个 $[0,N-1]$ 之间的整数。
第 $r$ 行第 $c$ 列（其中 $c < N$）的整数对应的情况下为强盗的回合，警察在街角 $r$ 而强盗已经移动到街角 $c$。
主对角线将被忽略。
第 $r$ 行的最后一个整数表示如果警察从街角 $r$ 开始则强盗开始的街角为该数。

---

数据范围与提示

子任务编号	分数	数据范围	附加条件
1	16	$1 \le N \le 500$	对于每两个街角，只有一条路线可以互相到达
2	14	$N$ 可变	街角与小巷形成的网络为网格形结构
3	30	$2 \le N \le 100$	无
4	40	$2 \le N \le 500$

你的函数实现须满足下述要求：

1. 确定警察能否抓到强盗；
2. 如果警察有可能抓到强盗的话，表示警察可以通过移动抓到强盗。

在子任务 1 与 2 中，你的解决方案应该满足以上要求才能拿到所有分数。
在子任务 3 与 4 中，若你的解决方案只满足要求 1，可以拿到 $30\%$ 的子任务分数。如果你的程序只打算拿部分分，则可以通过输出无效的移动来终止程序（例如，使 nextMove 返回 -1）。