#214507. [JOISC 2017] 自然公园 / Natural Park

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

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

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

你将提供两个地点 、 以及若干中间地点给 IOI 女士，并询问：若仅允许经过给定的中间地点，是否可能从地点 到达地点 ？随后，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)

  该函数仅被调用一次。

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

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

• void Answer(int A, int B)

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

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

  参数应满足以下条件：

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

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

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

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

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

  参数应满足以下条件：

  • 。
  • （）。
  • 。
  • 。

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

函数 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。

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

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

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

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

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

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

样例输入 1

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

样例输出 1

示例调用

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

:::align{center}

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

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

约束条件

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

• 。
• 。
• 。
• 对于每个地点，最多有 7 条道路连接它与其他地点。
• 若允许经过若干条道路，则可以从任意地点到达其他任意地点。
• 对于任意两个不同的地点，最多只有一条道路连接它们。

子任务

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

子任务 1 [10 分]

• 。
• 。

子任务 2 [10 分]

• 。
• 。
• 对于地点 0 或 ，恰好有一条道路连接它与其他地点；对于其他每个地点，恰好有两条道路连接它与其他地点。

子任务 3 [27 分]

• 。
• 。
• 对于每个 （），若我们最多经过 8 个其他地点，则可以从地点 0 到达地点 。

子任务 4 [30 分]

• 。
• 。

子任务 5 [23 分]

• 。

翻译由 Qwen3-235B 完成