蚂蚁 Anthony 住在 JOI 市。JOI 市有 $N$ 个城镇，编号为 $0$ 到 $N-1$。Anthony 住在城镇 $0$。市里有 $M$ 条道路，编号为 $0$ 到 $M-1$。道路 $i$ ($0 \le i \le M-1$) 连接城镇 $U_i$ 和 $V_i$，且可以双向通行。不同的道路连接不同的城镇对。通过若干条道路，可以从任意城镇到达其他任何城镇。
猫 Catherine 是 Anthony 的朋友。她计划访问 JOI 市，但她不了解道路信息，且经常迷路。Anthony 决定提前在道路上设置标记。标记共有 $A$ 种，编号为 $0$ 到 $A-1$。
现在 Catherine 到达了 JOI 市的某个城镇。每当她处于除城镇 $0$ 以外的城镇时，她会执行以下操作：
对于每种标记，她可以统计从她当前城镇出发的道路中，该种标记的道路数量（不包括她最后经过的那条道路，如果存在的话）。
之后，她选择一条道路通行。注意，除了最后经过的道路外，她只能通过标记类型来区分道路。通过适当地选择道路，她希望在不花费太多时间的情况下到达城镇 $0$。更准确地说，如果从她初始城镇到城镇 $0$ 的最少道路数为 $d$，她希望通过选择不超过 $d+B$ 次道路到达城镇 $0$。
请编写一个程序，根据道路信息实现 Anthony 设置标记的策略，以及一个实现 Catherine 选择道路的策略的程序。
实现细节
你需要提交两个文件。
第一个文件是 Anthony.cpp。它实现了 Anthony 的策略，并应实现以下函数。程序应包含 Anthony.h。
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V)
该函数在开始时被调用且仅被调用一次。 参数 $N$ 是城镇数量 $N$。 参数 $M$ 是道路数量 $M$。 参数 $A$ 是标记类型数量 $A$。 参数 $B$ 是 Catherine 选择道路次数的余量。 参数 $U$ 和 $V$ 是长度为 $M$ 的数组，其中 $U[i]$ 和 $V[i]$ 是道路 $i$ 连接的城镇 $U_i$ 和 $V_i$ ($0 \le i \le M-1$)。 返回值 $x$ 应为一个长度为 $M$ 的数组。如果长度不为 $M$，你的程序将被判为 Wrong Answer [1]。值 $x[i]$ ($0 \le i \le M-1$) 表示道路 $i$ 上的标记。必须满足不等式 $0 \le x[i] \le A-1$。如果不满足，你的程序将被判为 Wrong Answer [2]。
第二个文件是 Catherine.cpp。它实现了 Catherine 的策略，并应实现以下函数。程序应包含 Catherine.h。
void Init(int A, int B)
该函数在开始时被调用且仅被调用一次。 参数 $A$ 是标记类型数量 $A$。 参数 $B$ 是 Catherine 选择道路次数的余量。
int Move(std::vector<int> y)
每当 Catherine 到达除城镇 $0$ 以外的城镇时，该函数会被调用。
参数 $y$ 是一个长度为 $A$ 的数组，其中 $y[j]$ 是从她当前城镇出发且标记为 $j$ 的道路数量 ($0 \le j \le A-1$)，不包括她最后经过的那条道路（如果存在的话）。
返回值 $z$ 应满足 $-1 \le z \le A-1$。如果不满足，你的程序将被判为 Wrong Answer [3]。如果 $z = -1$，她将折返，选择她最后经过的那条道路。如果 $0 \le z \le A-1$，她将选择一条标记为 $z$ 的道路。当 Move 函数第一次被调用时，如果 $z = -1$，你的程序将被判为 Wrong Answer [4]。如果 $0 \le z \le A-1$ 且 $y[z] = 0$，你的程序将被判为 Wrong Answer [5]。
如果 Catherine 选择了一条与她最后经过的道路不同的道路，她实际经过的道路将是 Move 函数返回值所指定的标记对应的道路之一。注意，这种选择可能不是随机的。
如果 Catherine 在经过 $d+B$ 次道路后仍未到达城镇 $0$（即 Move 函数被调用了 $d+B$ 次），你的程序将被判为 Wrong Answer [6]。
重要提示
- 你的程序可以实现其他内部函数或使用全局变量。提交的文件将与评测程序一起编译，成为一个单一的可执行文件。所有全局变量和内部函数应声明在匿名命名空间中，以避免与其他文件冲突。评测时，它将作为 Anthony 和 Catherine 两个进程执行。Anthony 和 Catherine 的进程不能共享全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
数据范围
- $2 \le N \le 20\,000$。
- $1 \le M \le 20\,000$。
- $1 \le S \le N-1$（$S$ 是 Catherine 最初到达的城镇编号）。
- $0 \le U_i < V_i \le N-1$ ($0 \le i \le M-1$)。
- $(U_i, V_i) \neq (U_j, V_j)$ ($0 \le i < j \le M-1$)。
- 通过若干条道路，可以从任意城镇到达其他任何城镇。
子任务
- (2 分) $A = 4, B = 0, M = N - 1$。
- (2 分) $A = 4, B = 0$。
- (2 分) $A = 3, B = 0, M = N - 1$。
- (9 分) $A = 3, B = 0$。
- (5 分) $A = 2, B = 2N, M = N - 1, 6 \le N \le 500$。
- (71 分) $A = 2, B = 12, M = N - 1$。
- (9 分) $A = 2, B = 6, M = N - 1$。
样例
样例输入 1
7 6 2 6 1 0 2 0 4 1 2 1 3 1 5 4 6
说明
在此样例通信中，Catherine 依次访问城镇 1, 5, 1, 2, 0。我们有 $d = 2$。Catherine 移动了 4 次。 此样例输入满足子任务 7 的约束。