JOI 王国有很多城市，城市之间由双向道路连接。道路系统满足以下条件：

• 城市被标号为 $0$ 到 $N - 1$（其中 $N$ 为城市总数）。
• 有且仅有 $N - 1$ 条道路，且从任一城市出发都能经过若干条道路抵达其它所有城市。
• 从 $0$ 到其它任何城市都只需经过不超过 $18$ 条道路。

在 JOI 王国，每天都会有很多人从城市 $0$ 向其它城市出发。由于很多人有两个目的地，他们时常会问以下问题：对于两个不同城市 $X, Y$，以下哪个条件满足？

(0) 要抵达 $X$ 就必须经过 $Y$；

(1) 要抵达 $Y$ 就必须经过 $X$；

(2) 以上两者均不满足。

容易发现上述情形中 (0), (1), (2) 总是恰有一条满足。特别地，当 $Y = 0$ 时我们认为满足的条件是 $(0)$；$X = 0$ 的情况类似。

事实上，其它国家的道路系统往往也满足 1~3。因此，JOI 王国的人们希望开发以下两个程序从而解决一般性的问题：

• (程序 1) 给定城市个数 $N$ 和所有道路信息，该程序会给每个城市确定一个 $[0, 2^{60} - 1]$ 内的编码。

• (程序 2) 给定城市 $X$ 和 $Y$ 对应编码，该程序会回答对应的问题（即返回三种情况之一）。

注意运行程序 2 时并不会直接给出 $N$ 和道路信息。

请实现以上两个程序。

实现细节

本题仅支持 C/C++ 语言。

你需要提交两个文件。

第一个文件名应为 Encoder.c 或 Encoder.cpp。该文件为你对程序 1 的实现。请包含头文件 Encoder.h。

你需要实现以下函数：

• void Encode(int N, int A[], int B[])
  • 每组测试数据中，该函数会被调用恰好一次。
  • 参数 $\texttt{N}$ 表示城市个数。
  • 数组 $\texttt{A[]}$ 和 $\texttt{B[]}$ 的长度均为 $N - 1$，表示对每个 $i \in [0, N - 2]$，城市 $\texttt{A[i]}$ 和 $\texttt{B[i]}$ 之间有一条道路。

你可以调用以下函数：

• void Code(int city, long long code)
  • 该函数用于给城市指定编码。
  • 你需要保证 $\texttt{city} \in [0, N - 1]$，否则会被判为 Wrong Answer[1]。你还需要保证每次调用时 $\texttt{city}$ 的取值不同，否则会被判为 Wrong Answer[2]。
  • 你还需要保证 $\texttt{code} \in [0, 2^{60} - 1]$，否则会被判为 Wrong Answer[3]。

你的程序应当调用 $\texttt{Code}$ 恰好 $N$ 次，否则会被判为 Wrong Answer[4]。

若以上过程中你的程序被判为 Wrong Answer，它会被立即终止。

第二个文件名应为 Device.c 或 Device.cpp。该文件为你对程序 1 的实现。请包含头文件 Device.h。

你需要实现以下函数：

• void InitDevice()

  • 每组测试数据中，该函数会被调用恰好一次（且是在 $\texttt{Answer}$ 被调用之前）。

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

  • 该函数中，你需要回答询问。
  • 参数 $\texttt{S}$ 和 $\texttt{T}$ 为 $X$ 和 $Y$ 在 $\texttt{Encode}$ 中被给予的编号。
  • 若 $0$ 到 $X$ 的任何路径都经过 $Y$，该函数应返回 $0$。
  • 若 $0$ 到 $Y$ 的任何路径都经过 $X$，该函数应返回 $1$。
  • 否则，该函数应返回 $2$。
  • 若 $\texttt{Answer}$ 的返回值不在 $[0, 2]$ 内，你会被判为 Wrong Answer[5]；答案错误则会被判为 Wrong Answer[6]。

评分方式

评分方式如下：

若你的程序被判定为 Wrong Answer，它会被立即终止。

(1) 函数 $\texttt{Encode}$ 会被调用恰好一次。

(2) 函数 $\texttt{InitDevice}$ 会被调用恰好一次。

(3) 对每个测试点，程序 2 会被进行 $Q$ 次询问。对于第 $j (j \in [1, Q])$ 次询问，$\texttt{Answer}(S_j, T_j)$ 会被调用，其中 $S_j$ 和 $T_j$ 分别为城市 $X_j$ 和 $Y_j$ 的编号。

(4) 上述过程结束后，你的程序会被判为正确。

注意事项

• 运行时间和空间是对于以上整个过程计算的。注意 $\texttt{Answer}$ 函数会被调用 $Q$ 次。

• 你的程序不应当在上述过程中返回 Wrong Answer 或 Runtime Error。

• 你的程序可以调用自己实现的内部函数或使用全局变量。被提交的程序会被使用同一 grader 编译成单个可执行文件。全局变量和内部函数应用 static 定义以避免重名。

• 评分时两个程序可被视为独立的部分，因而不能共用全局变量。

• 你的程序不应当向标准输入输出或其他文件进行任何读写操作。

测试程序方式

「附加文件」中提供了 Encoder.h、Device.h、grader.c 和 grader.cpp 四个文件。若你编写的程序名称为 Encoder/Device.c 或 Encoder/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。

注意实际评测时的程序与下发的样例评测程序并不相同。实际的 grader 实现将通过标准输入输出进行通信。

样例评测程序输入格式

样例评测程序将从标准输入读入以下数据。

• 第 $1$ 行两个整数 $N, Q$，表示城市和询问个数。

• 接下来的 $N - 1$ 行中，第 $i + 1(0 \leq i \leq N - 2)$ 行两个整数 $A_i, B_i$，表示一条道路。

• 接下来的 $Q$ 行中，第 $j$（$1 \leq j \leq Q$）行包含两个空格分隔的整数 $X_j, Y_j, E_j$，表示进行一次关于 $X_j$ 和 $Y_j$ 的询问，正确答案为 $E_j$。

样例评测程序输出格式

样例评测程序将向标准输出输出以下信息。

• 判为正确时，输出形如 Accepted: max_code=123456 的信息；

• 运行过程中被判为错误时，以 Wrong Answer [x] 的格式报告并退出。

程序执行过程中违反了多种限制时，只会报告其中的一种。

数据范围与提示

• $2 \leq N \leq 250 000$。

• $1 \leq Q \leq 250 000$。

• $0 \leq A_i \leq N - 1 (0 \leq i \leq N - 2)$。

• $0 \leq B_i \leq N - 1 (0 \leq i \leq N - 2)$。

• $A_i, B_i (0 \leq i \leq N - 2)$。

• 从城市 $0$ 出发经过不超过 $18$ 条道路可抵达任何城市。

• $0 \leq X_j \leq N - 1 (1 \leq j \leq Q)$。

• $0 \leq Y_j \leq N - 1 (1 \leq j \leq Q)$。

• $X_j\neq Y_j (1 \leq j \leq Q)$。

子任务 1（8 分）

• $N \leq 10$。

子任务 2（92 分）

无特殊限制。该子任务的得分按以下方式计算：

• 记 $L$ 为所有城市的最大编码。
  • $L \geq 2^{38}$ 时记 $0$ 分。
  • $2^{36} \leq L \leq 2^{38} - 1$ 时记 $10$ 分。
  • $2^{35} \leq L \leq 2^{36} - 1$ 时记 $14$ 分。
  • $2^{34} \leq L \leq 2^{35} - 1$ 时记 $22$ 分。
  • $2^{28} \leq L \leq 2^{34} - 1$ 时记 $\lfloor 372 - 10 \log_2(L + 1) \rfloor$ 分（其中 $\lfloor x \rfloor$ 为下取整）。
  • $L \leq 2^{28} - 1$ 时记 $92$ 分。
  • 注意当 $L \geq 2^{38}$ 时，评测系统有可能显示 Accepted: 0 points 或 Wrong Answer。