背景

评测说明（请仔细阅读）

1. 不要 ${\texttt{\#include}}$。
2. 请使用 $\red{\texttt{C++20}}$。
3. 在文件头粘贴如下的内容：

void Code(int city, long long code);

题目描述

JOI 王国内有许多城市。道路网络满足以下条件：

• （条件 1）城市编号从 $0$ 到 $N - 1$。其中，$N$ 是 JOI 王国内的城市总数。
• （条件 2）城市之间由 $N - 1$ 条道路连接。每条道路均可双向通行，且通过若干条道路，可以从任意城市到达其他任意城市。
• （条件 3）从城市 $0$ 出发，最多经过 $18$ 条道路即可到达任意其他城市。

每天，在 JOI 王国，许多人从城市 $0$ 出发前往其他城市。由于许多人有两个目的地，他们有时会提出以下查询：对于两个不同的城市 $X$、$Y$，以下哪一项（$0$）、（$1$）、（$2$）成立？

• （$0$）当我们从城市 $0$ 前往城市 $X$ 时，必定会经过城市 $Y$。
• （$1$）当我们从城市 $0$ 前往城市 $Y$ 时，必定会经过城市 $X$。
• （$2$）以上两项（$0$）和（$1$）均不成立。

注意，在上述情形中，（$0$）、（$1$）、（$2$）中恰好有一项成立。当 $X = 0$ 时，无论 $Y$ 取何值，我们均认为（$1$）成立；类似地，当 $Y = 0$ 时，无论 $X$ 取何值，我们均认为（$0$）成立。

已知，正如 JOI 王国的道路网络一样，上述条件 1–3 在其他国家也成立。在 JOI 王国，人们计划开发以下两台机器，以便它们也可在其他国家使用：

• （机器 1）给定城市数量 $N$ 和道路网络信息，该机器为每个城市分配一个编码。编码是一个介于 $0$ 到 $2^{60} - 1$（含）之间的整数。
• （机器 2）给定由机器 1 分配的两个不同城市 $X$、$Y$ 的编码，该机器回答查询。

若分配的编码为大整数，则处理起来较为困难。我们希望开发的机器能分配较小的值作为编码。

注意，当使用机器 2 时，城市数量 $N$ 和道路网络信息不会直接提供给机器。

任务

为了开发上述两台机器，请编写以下两个程序：

• 给定 JOI 王国内的城市数量 $N$ 和道路网络信息，第一个程序为每个城市分配一个编码。
• 给定由第一个程序分配的两个不同城市的编码，第二个程序回答针对这些城市的查询。

实现细节

你需要提交两个使用相同编程语言编写的文件。

第一个文件为 Encoder.c 或 Encoder.cpp，该文件实现机器 1。它应实现以下函数，并且程序应包含 Encoder.h。

• void Encode(int N, int A[], int B[])

  对于每个测试用例，该函数被调用一次。

  • 参数 $N$ 表示城市数量。
  • 参数 $A[]$、$B[]$ 是长度为 $N - 1$ 的整数序列，用于描述道路网络。元素 $A[i]$、$B[i]$（$0 \le i \le N - 2$）表示城市 $A[i]$ 与城市 $B[i]$ 之间有一条直接相连的道路。

你的程序应调用以下函数：

• void Code(int city, long long code)

  该函数为城市分配编码。

  • 参数 city 是被分配编码的城市编号，其值应为介于 $0$ 到 $N - 1$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被判定为 Wrong Answer[1]。若使用相同的参数调用该函数两次，你的程序将被判定为 Wrong Answer[2]。
  • 参数 code 是分配给编号为 city 的城市的编码，其值应为介于 $0$ 到 $2^{60} - 1$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被判定为 Wrong Answer[3]。

你的程序应恰好调用函数 Code $N$ 次。若函数 Encode 结束时调用 Code 的次数不为 $N$，你的程序将被判定为 Wrong Answer[4]。

若对函数 Encode 的调用被判定为错误答案，你的程序将立即终止。

第二个文件为 Device.c 或 Device.cpp，该文件实现机器 2。它应实现以下函数，且程序应包含 Device.h。

• void InitDevice()

  该函数初始化机器 2。函数 InitDevice 在调用以下函数 Answer 之前被调用一次。

• int Answer(long long S, long long T)

  该函数回答每个查询。对于每个查询，函数 Answer 被调用一次。

  • 参数 $S$、$T$ 是由函数 Encode 分配给两个不同城市 $X$、$Y$ 的编码。

  • 为回答查询，函数 Answer 的返回值应满足以下条件：

    • 若从城市 $0$ 前往城市 $X$ 时必定经过城市 $Y$，则返回值应为 $0$。
    • 若从城市 $0$ 前往城市 $Y$ 时必定经过城市 $X$，则返回值应为 $1$。
    • 否则，返回值应为 $2$。

  因此，函数 Answer 的返回值应为介于 $0$ 到 $2$（含）之间的整数。若返回值超出此范围，你的程序将被判定为 Wrong Answer[5]。若返回值在此范围内但不满足上述条件，你的程序将被判定为 Wrong Answer[6]。

评分流程

评分按以下方式进行。若你的程序被判定为错误答案，则立即终止。

（1）函数 Encode 被调用一次。

（2）函数 InitDevice 被调用一次。

（3）对于每个测试用例，机器 2 会收到 $Q$ 个查询。对于第 $j$ 个查询（$1 \le j \le Q$），函数 Answer 被调用，其参数 $S$ 为 $S_j$，参数 $T$ 为 $T_j$，其中 $S_j$、$T_j$ 分别是由函数 Encode 分配给城市 $X_j$、$Y_j$ 的编码。

（4）你的程序被视为正确。

重要提示

• 运行时间和内存使用量根据评分流程中的（1）、（2）、（3）计算。注意，在流程（3）中，函数 Answer 总共被调用 $Q$ 次。
• 你的程序在流程（1）中调用函数 Encode、在流程（2）中调用函数 InitDevice、或在流程（3）中调用函数 Answer 时，均不得被判定为 Wrong Answer。你的程序必须在无运行时错误的情况下执行。
• 你的程序可以为内部使用实现其他函数，或使用全局变量。提交的程序将与评分器一起编译，并生成一个可执行文件。所有全局变量和内部函数应声明为 static，以避免与其他文件发生冲突。机器 1 和机器 2 的程序在评分时将作为两个独立的进程运行，它们不能共享全局变量。
• 你的程序不应使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。

编译与测试运行

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

示例评分器由一个源文件组成，该源文件为 grader.c 或 grader.cpp。例如，若你的程序为 Encoder.c 和 Device.c，或 Encoder.cpp 和 Device.cpp，你可以运行以下命令来编译你的程序：

• C

  gcc -std=c11 -O2 -o grader grader.c Encoder.c Device.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Encoder.cpp Device.cpp

当编译成功后，将生成可执行文件 grader。注意，实际评分器与示例评分器不同。示例评分器将以单个进程形式运行，它将从标准输入读取输入数据，并将结果写入标准输出。

输入格式

示例评分器从标准输入读取以下数据：

• 第一行包含两个以空格分隔的整数 $N$、$Q$。这表示共有 $N$ 个城市，以及给出 $Q$ 个查询。
• 接下来的 $N - 1$ 行中，第 $(i + 1)$ 行（$0 \le i \le N - 2$）包含两个以空格分隔的整数 $A_i$、$B_i$。这表示城市 $A_i$ 与城市 $B_i$ 之间有一条直接相连的道路。
• 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含三个以空格分隔的整数 $X_j$、$Y_j$、$E_j$。这表示在第 $j$ 个查询中，$X = X_j$ 且 $Y = Y_j$；若你的程序对该查询的回答与 $E_j$ 不同，示例评分器将判定你的程序为 Wrong Answer。

输出格式

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

• 若你的程序被视为正确，示例评分器将以如下格式输出所分配编码的最大值：“Accepted : max_code=123456”。
• 若你的程序被视为错误答案，示例评分器将以如下格式输出其错误类型：“Wrong Answer [1]”。

若你的程序被视为多种类型的错误答案，示例评分器仅报告其中一种。

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

提示

样例 1 解释

函数 Encode(...) 将使用以下参数被调用：

参数	Encode(...)
$N$	$6$
$A$	$\{4, 0, 4, 3, 3\}$
$B$	$\{1, 3, 5, 2, 4\}$

Machine 1	Machine 2
Encode(...)
Code(0,0)
Code(2,4)
Code(4,16)
Code(1,1)
Code(3,9)
Code(5,25)
	InitDevice()
	Answer(4,16)
	Answer(1,0)
	Answer(25,1)
	Answer(25,9)
	Answer(16,1)

数据范围

所有输入数据满足以下条件。关于 $N$、$Q$、$A_i$、$B_i$、$X_j$、$Y_j$ 的含义，请参见“示例评分器的输入”。

• $2 \le N \le 250000$。
• $1 \le Q \le 250000$。
• $0 \le A_i \le N - 1$（$0 \le i \le N - 2$）。
• $0 \le B_i \le N - 1$（$0 \le i \le N - 2$）。
• $A_i \ne B_i$（$0 \le i \le N - 2$）。
• 从城市 $0$ 出发，最多经过 $18$ 条道路即可到达任意其他城市。
• $0 \le X_j \le N - 1$（$1 \le j \le Q$）。
• $0 \le Y_j \le N - 1$（$1 \le j \le Q$）。
• $X_j \ne Y_j$（$1 \le j \le Q$）。

子任务

共有 2 个子任务。每个子任务的得分及额外约束如下：

子任务 1 [8 分]

• $N \le 10$。

子任务 2 [92 分]

无额外约束。在本子任务中，得分按如下方式计算：

• 设 $L$ 为本子任务所有测试用例中分配给城市的编码的最大值。

• 本子任务的得分为：

  • 若 $2^{38} \le L$，得 $0$ 分。
  • 若 $2^{36} \le L \le 2^{38} - 1$，得 $10$ 分。
  • 若 $2^{35} \le L \le 2^{36} - 1$，得 $14$ 分。
  • 若 $2^{34} \le L \le 2^{35} - 1$，得 $22$ 分。
  • 若 $2^{28} \le L \le 2^{34} - 1$，得 $\lfloor 372 - 10 \log_2(L + 1) \rfloor$ 分。其中，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
  • 若 $L \le 2^{28} - 1$，得 $92$ 分。

请注意，若 $2^{38} \le L$，本子任务的结果在竞赛系统中可能显示为“Accepted : 0 points”或“Wrong Answer”。

翻译由 Qwen3-235B 完成