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

你可以调用以下函数：

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

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

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

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

你需要实现以下函数：

• void InitDevice()

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

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

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

评分方式

评分方式如下：

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

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

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

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

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

注意事项

• 运行时间和空间是对于以上整个过程计算的。注意 $\mathtt{\text{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\le i\le N-2)$ 行两个整数 $A_i,B_i$，表示一条道路。

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

样例评测程序输出格式

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

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

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

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

数据范围与提示

• $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,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)$。

子任务 1（8 分）

• $N\le 10$。

子任务 2（92 分）

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

• 记 $L$ 为所有城市的最大编码。
  • $L\ge 2^{38}$ 时记 $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$ 为下取整）。
  • $L\le 2^{28}-1$ 时记 $92$ 分。
  • 注意当 $L\ge 2^{38}$ 时，评测系统有可能显示 Accepted: 0 points 或 Wrong Answer。