Pak Dengklek 住在印度尼西亚，这个国家由 $N$ 个城镇组成，编号从 $0$ 到 $N - 1$。对于每一对城镇，都有且仅有一条单向道路连接它们。Pak Dengklek 不知道这些道路的方向，但 Pak Chanek 主动提出要帮助他。

Pak Dengklek 最多可以向 Pak Chanek 提出 $40\,000$ 个问题。对于每个问题，Pak Dengklek 选择一对城镇，Pak Chanek 会告诉他连接这两座城镇的道路方向。

Pak Dengklek 想要知道是否存在一个出度最多为 $1$ 的城镇，如果存在，请返回该城镇的编号；如果不存在，请报告。如果有多个这样的城镇，Pak Dengklek 只需返回其中任意一个即可。

实现细节

你需要实现以下函数：

int find_town(int N)

• $N$：印度尼西亚的城镇数量。
• 该函数应返回任意一个出度最多为 $1$ 的城镇编号，如果不存在，则返回 $-1$。
• 该函数将被调用恰好一次。

上述函数可以调用以下函数：

bool check_road(int A, int B)

• $A, B$：询问 Pak Chanek 的一对城镇编号。
• $A$ 和 $B$ 必须是 $0$ 到 $N - 1$ 之间（包含 $0$ 和 $N-1$）的相异整数。
• 如果存在从城镇 $A$ 到城镇 $B$ 的道路，则返回 true；如果存在从城镇 $B$ 到城镇 $A$ 的道路，则返回 false。
• 该函数最多可被调用 $40\,000$ 次。

样例

样例 1

考虑一个有 $3$ 个城镇的场景，城镇间的道路如下图所示：

函数 find_town 的调用方式如下：

find_town(3)

该函数可能会调用 check_road(0, 1)，在此场景下返回 true。此时，已有足够的信息得出城镇 $1$ 的出度最多为 $1$。因此，该函数可以返回 $1$。

此外，该函数也可能调用 check_road(2, 1)，在此场景下返回 false。此时，已有足够的信息得出城镇 $2$ 的出度最多为 $1$。因此，该函数也可以返回 $2$。

样例 2

考虑一个有 $5$ 个城镇的场景，城镇间的道路如下图所示：

函数 find_town 的调用方式如下：

find_town(5)

在此场景中，不存在出度最多为 $1$ 的城镇。因此，该函数应返回 $-1$。

数据范围

• $3 \le N \le 2000$

子任务

1. (10 分) $N \le 250$
2. (90 分) 无附加限制。

在子任务 2 中，你可以获得部分分数。设 $Q$ 为该子任务中所有测试用例对 check_road 函数调用的最大次数。该子任务的得分计算如下表所示：

评测说明

在某些测试用例中，评测程序的行为是自适应的。这意味着在这些测试用例中，评测程序没有固定的道路方向配置。相反，评测程序给出的答案可能取决于你的解法所提出的问题。保证评测程序在回答时，每次回答后至少存在一种与目前所有回答一致的道路方向配置。

样例评测程序

样例评测程序读取一个包含 $N$ 个字符串的数组 $R$，每个字符串包含 $N$ 个字符，表示印度尼西亚的道路。对于满足 $0 \le i, j \le N - 1$ ($i \neq j$) 的每一对 $i$ 和 $j$，如果存在从城镇 $i$ 到城镇 $j$ 的道路，则 $R[i][j]$ 为 $1$；如果存在从城镇 $j$ 到城镇 $i$ 的道路，则 $R[i][j]$ 为 $0$。对于满足 $0 \le i \le N - 1$ 的每个 $i$，$R[i][i]$ 应为 $0$。

样例评测程序按以下格式读取输入：

• 第 1 行：$N$
• 第 $2 + i$ 行 ($0 \le i \le N - 1$)：$R[i]$

如果样例评测程序检测到协议违规，它将输出 Protocol Violation: <MSG>，其中 <MSG> 为以下内容之一：

• too many questions: check_road 被调用超过 $40\,000$ 次。
• invalid parameters: check_road 被调用时，$A$ 和 $B$ 不是 $0$ 到 $N - 1$ 之间的相异整数。

否则，样例评测程序的输出格式如下：

• 第 1 行：find_town 的返回值。
• 第 2 行：check_road 的调用次数。

注意，样例评测程序不是自适应的。