题目描述

JOI 岛是一个观光区，整座岛屿被指定为自然公园。

JOI 岛上有 $N$ 个地点和若干条道路。这些地点从 $0$ 到 $N-1$ 编号。每条道路连接两个不同的地点，且可双向通行。每个地点最多连接 7 条道路。任意两个不同地点之间至多仅有一条道路相连。只要经过若干条道路，我们便可从任意地点到达其他任意地点。

你和你的朋友 IOI 女士将共同调查 JOI 岛。为高效完成调查，你需要弄清 JOI 岛的结构。JOI 岛十分危险，因为岛上栖息着许多野生动物。由于 IOI 女士拥有出色的运动能力，她将负责实地探索 JOI 岛，而你则根据 IOI 女士的报告来确定 JOI 岛的结构。

你将提供两个地点 $A$、$B$ 以及若干中间地点给 IOI 女士，并询问：若仅允许经过给定的中间地点，是否可能从地点 $A$ 到达地点 $B$？随后，IOI 女士将探索 JOI 岛，并将结果报告给你。

由于调查时间不能过长，查询次数应小于或等于 45000。

任务

编写一个程序，与 IOI 女士通信并确定 JOI 岛的结构。

实现细节

你需要编写一个程序，实现确定 JOI 岛结构的方法。你的程序应当声明函数 void Answer(int A, int B); 和 int Ask(int A, int B, int Place[]);，并且使用不低于 C++17 的语言标准提交试题。

你的程序应实现以下函数：

• void Detect(int T, int N)

  该函数仅被调用一次。

  • 参数 $T$ 为子任务编号，$N$ 为地点数量。

你的程序应通过调用以下函数，输出其确定的 JOI 岛结构：

• void Answer(int A, int B)

  调用该函数的次数应等于 JOI 岛中道路的总数。

  • 参数 $A$、$B$ 表示存在一条连接地点 $A$ 与地点 $B$ 的道路。

  参数应满足以下条件：

  • $A$、$B$ 应满足 $0 \le A < B \le N-1$。若此条件不满足，你的程序将被判定为 Wrong Answer[1]。
  • 若函数以参数 $(A, B)$ 被调用，则必须存在一条连接地点 $A$ 与地点 $B$ 的道路。若此条件不满足，你的程序将被判定为 Wrong Answer[2]。
  • 函数不应以相同的参数 $(A, B)$ 被调用超过一次。若此条件不满足，你的程序将被判定为 Wrong Answer[3]。

此外，你的程序可调用以下函数：

• int Ask(int A, int B, int Place[])

  该函数用于向 IOI 女士提问。

  • Place 是一个数组的指针，表示可能经过的中间地点。对于每个 $i$（$0 \le i \le N-1$），若 Place[i] = 1，表示可经过地点 $i$；若 Place[i] = 0，表示不可经过地点 $i$。
  • 若仅允许经过数组 Place[] 中指定的某些地点，可以从地点 $A$ 到达地点 $B$，则该函数返回值为 1；否则返回值为 0。

  参数应满足以下条件：

  • $0 \le A < B \le N-1$。
  • $0 \le \text{Place}[i] \le 1$（$0 \le i \le N-1$）。
  • $\text{Place}[A] = 1$。
  • $\text{Place}[B] = 1$。

若上述条件未被满足，你的程序将被判定为 Wrong Answer[4]。然而，若数组 Place[] 的长度不等于 $N$，该函数的行为无法保证。

函数 Ask 的调用次数不得超过 45000 次。若超出，你的程序将被判定为 Wrong Answer[5]。

当函数 Detect 执行完毕后，若存在某条道路未作为先前对函数 Answer 的调用参数出现，则你的程序将被判定为 Wrong Answer[6]。

你的程序可实现其他函数供内部使用，或使用全局变量。你的程序不得使用标准输入和标准输出，也不得通过任何方式与其他文件通信。

编译与测试运行

你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的示例评测程序。该归档文件还包含你的程序的一个示例源代码文件。

一个示例评测程序由一个源文件组成，该文件名为 grader.c 或 grader.cpp。例如，如果你的程序名为 park.c 或 park.cpp，你可以运行以下命令来编译你的程序。

• C
  gcc -std=c11 -O2 -o grader grader.c park.c -lm

• C++
  g++ -std=c++14 -O2 -o grader grader.cpp park.cpp

当编译成功后，将生成可执行文件 grader。

请注意，实际的评测程序与示例评测程序不同。示例评测程序将以单个进程运行，从标准输入读取输入数据，并将结果写入标准输出。

输入格式

示例评测程序从标准输入读取以下数据：

• 第一行输入包含一个整数 $T$，表示子任务编号。
• 第二行输入包含一个整数 $N$，表示地点数量。
• 第三行输入包含一个整数 $M$，表示道路数量。
• 在接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含两个以空格分隔的整数 $A_i$、$B_i$。这表示存在一条连接地点 $A_i$ 与地点 $B_i$ 的道路，且该道路可双向通行。

输出格式

当程序成功终止时，示例评测程序将向标准输出写入以下信息。（引号实际不会输出。）

• 若你的程序被视为正确，示例评测程序将输出 “Accepted.”。
• 若你的程序被视为 Wrong Answer，示例评测程序将按以下格式输出其类型：“Wrong Answer [1]”，随后你的程序将被终止。

若你的程序被视为多种类型的 Wrong Answer，示例评测程序仅报告其中一种。

1
6
7
0 1
0 3
1 2
1 4
2 4
2 5
3 4

提示

示例调用

调用	返回值
Ask(3, 5, {0,0,1,1,1,1})	1
Answer(2, 4)
Answer(2, 5)
Answer(3, 4)
Ask(0, 4, {1,0,1,0,1,0})	0
Answer(0, 1)
Answer(0, 3)
Answer(1, 4)
Answer(1, 2)

请注意，本示例中的函数调用不一定具有实际意义。在本示例中，函数 Detect 以参数 $T = 1$、$N = 6$ 被调用。在本示例中，JOI 岛屿的结构如下：

:::align{center}

JOI 岛屿的结构。
圆圈和数字表示地点及其编号，线段表示道路。 :::

• 第一次调用函数 Ask 是询问：若仅允许经过地点 2、3、4、5，是否可以从地点 3 到达地点 5。由于可行，函数 Ask 返回 1。
• 第二次调用函数 Ask 是询问：若仅允许经过地点 0、2、4，是否可以从地点 0 到达地点 4。由于不可行，函数 Ask 返回 0。

约束条件

所有输入数据均满足以下条件。关于 $T$、$N$、$M$ 的含义，请参见“示例评测程序的输入”。

• $1 \le T \le 5$。
• $2 \le N \le 1400$。
• $1 \le M \le 1500$。
• 对于每个地点，最多有 7 条道路连接它与其他地点。
• 若允许经过若干条道路，则可以从任意地点到达其他任意地点。
• 对于任意两个不同的地点，最多只有一条道路连接它们。

子任务

共有 5 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [10 分]

• $T = 1$。
• $N \le 250$。

子任务 2 [10 分]

• $T = 2$。
• $M = N - 1$。
• 对于地点 0 或 $N-1$，恰好有一条道路连接它与其他地点；对于其他每个地点，恰好有两条道路连接它与其他地点。

子任务 3 [27 分]

• $T = 3$。
• $M = N - 1$。
• 对于每个 $i$（$1 \le i \le N - 1$），若我们最多经过 8 个其他地点，则可以从地点 0 到达地点 $i$。

子任务 4 [30 分]

• $T = 4$。
• $M = N - 1$。

子任务 5 [23 分]

• $T = 5$。

翻译由 Qwen3-235B 完成