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) 成立。

已知在其他国家，道路网络也满足上述条件 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$ 是城市数量 $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 是被分配代码的城市。参数 city 应为 $0$ 到 $N - 1$ 之间的整数（包含边界）。如果调用此函数时参数超出此范围，你的程序将被视为 Wrong Answer[1]。它不应被使用相同的参数调用两次。如果使用相同的参数调用两次，你的程序将被视为 Wrong Answer[2]。
• 参数 code 是分配给编号为 city 的城市代码。参数 code 应为 $0$ 到 $2^{60} - 1$ 之间的整数（包含边界）。如果调用此函数时参数超出此范围，你的程序将被视为 Wrong Answer[3]。

你的程序应恰好调用 Code 函数 $N$ 次。如果 Encode 函数终止时调用 Code 的次数不是 $N$，你的程序将被视为 Wrong Answer[4]。

如果 Encode 函数的调用被视为 Wrong Answer，你的程序将立即终止。

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

• void InitDevice()

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

• 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]。

评分方式

评分方式如下。如果你的程序被视为 Wrong Answer，它将立即终止。

(1) Encode 函数被调用一次。 (2) InitDevice 函数被调用一次。 (3) 对于每个测试用例，有 $Q$ 个询问提供给机器 2。对于第 $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。注意，实际的评测机与示例评测机不同。示例评测机将作为一个单一进程执行，它将从标准输入读取输入数据并将结果写入标准输出。

样例

样例通信

以下是示例评测机的输入及对应的函数调用。

函数 Encode(...) 被调用时参数如下：

输入格式 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

Accepted : max_code=25.

数据范围

所有输入数据满足以下条件。

• $2 \le N \le 250\,000$。
• $1 \le Q \le 250\,000$。
• $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 \neq 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 \neq 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”。