2022 年 10 月 8 日 更新：请注意，本题原始的交互库中，在 Alice 向 Bob 发送长度为 $0$ 的串时，会导致 Bob 的交互库在读入信息时失败。该问题已经修正，所有的提交记录均会被重测。感谢 hos_lyric 的反馈。

这是一道通信题。

一场考试正在进行。

这次考试的内容非常简单——给定一张 $N$ 个点 $M$ 条边的无向图 $G=(V,E)$，第 $i$ 条边（$0 \leq i < M$）的两端点为 $(U_i, V_i)$（$0 \leq U_i, V_i < N$）。保证图中不含有重边与自环。考试的任务是给每个点赋一个 $0 \sim 7$ 中的颜色 $C_i$，满足任意一条边的两个端点的颜色不同。

Alice 通过她的神力很快得到了一组合法的染色方案通过了考试。

Bob 也想要得到这样一个方案，于是它决定偷偷与 Alice 进行交流。Alice 可以向 Bob 发送一个长为 $L$ 的 0/1 串 $X$，向 Bob 提示一些信息。随后，Bob 需要构造出任意一个合法的 8 - 染色方案。

形式化的题意

两个程序各有一张无向图。第一个程序 Alice 拥有一个合法的 8 - 染色方案，它可以向第二个程序发送信息，使得第二个程序能够构造任意一个合法的 8 - 染色方案。

实现细节

这是一道通信题，本题仅支持 C++ 语言。你需要提交两个程序。

Alice

你需要提交的第一个程序为 Alice，其描述 Alice 的策略。

你需要包含头文件 Alice.h，并实现以下函数：

std::vector <int> Alice(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> C);

• 在每个测试点中，该函数会被调用恰好一次。
• N 表示图 $G$ 的点数 $N$。
• M 表示图 $G$ 的边数 $M$。
• U, V 均为长为 $M$ 的数组，描述图中的边。
• C 为一个长为 $N$ 的数组 $C_0, C_1, \cdots, C_{N-1}$（$0 \leq C_i < 8$），描述 Alice 所构造出的 8 - 染色中，第 $i$ 个点的颜色。
• 该函数需要返回一个数组 $X$：
  • 设 $L = |X|$。
  • 你需要保证 $0 \leq L < 6 \times 10^5$。
  • 你需要保证对任意 $0 \leq i < L$，均有 $X_i \in \{0, 1\}$
• 在每组测试数据中，该函数会被调用恰好一次。

Bob

你需要提交的第二个程序为 Bob，其描述 Bob 的策略。

你需要包含头文件 Bob.h，并实现以下函数：

std::vector <int> Bob(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> X);

• 在每个测试点中，该函数会被调用恰好一次。
• N 表示图 $G$ 的点数 $N$。
• M 表示图 $G$ 的边数 $M$。
• U, V 均为长为 $M$ 的数组，描述图中的边。
• X 为 Alice 所返回的数组 $X$。
• 该函数需要返回一个数组 $C'$：
  • 你需要保证 $|C'| = N$。
  • 你需要保证对任意 $0 \leq i < N$，均有 $0 \leq C'_i < 8$。
  • 你需要保证对任意 $0 \leq i < M$，均有 $C'_{U_i} \ne C'_{V_i}$。
• 在每组测试数据中，该函数会被调用恰好一次。

样例交互库

下发文件中含有样例交互库 grader.cpp，你可以通过以下命令编译得到可执行文件 answer：

g++ grader.cpp Alice.cpp Bob.cpp -o answer -O2

可执行文件将从标准输入（stdin）中读取以下格式的输入数据：

• 输入的第一行包含两个整数 $N, M$。
• 接下来 $M$ 行，每行两个整数 $U_i, V_i$。
• 接下来一行，包含 $N$ 个整数 $C_0, C_1, \cdots, C_{N-1}$。

若你的程序正常结束，则可执行文件将向标准输出中按照以下格式输出：

• 输出一行，包含 $N$ 个整数 $C'_0, C'_1, \cdots, C'_{N-1}$。

在最终评测时，程序 Alice 与 Bob 将被分别编译并在两个不同的进程中运行。本题的时间限制（1.0 秒）与空间限制（256 MiB）均指每个进程所能使用的时间与空间的最大值。在任意一个进程中超过该限制都会导致发生相应的错误。保证在最终评测时，三个程序各自的交互库使用的时间不超过 0.1 秒，空间不超过 16 MiB，即选手至少有 0.9 秒的时间与 240 MiB 的空间可用。

样例数据

样例输入

10 14
2 8
3 2
2 4
6 5
3 5
4 8
8 6
7 6
2 7
0 6
4 7
1 4
3 0
4 3
1 5 2 0 4 5 2 1 7 2

样例输出

0 0 0 1 2 0 1 3 3 0

子任务

请注意，本题满分为 75 分。

对于所有数据，$1 \leq N \leq 2 \times 10^{5}, 0 \leq M \leq 5 \times 10^5$。

在每个测试点中，如果你超出了时间限制（1.0 秒），超出了空间限制（256 MiB），或发生了运行时错误，或最终构造的方案不合法，则你的得分为 $0$。

• 请注意：时间限制指你的两个程序的运行时间的最大值不能超过 1.0 秒。空间限制指你的两个程序所使用的空间的最大值不能超过 256 MiB。
• 在任何合法（可以取得分数）的交互过程中，交互库在两次调用时所使用的内存不会超过 12 MiB，时间不会超过 0.05 秒。

否则，你的得分取决于 $L = |X|$ 的值：

• 参数 $S$ 与 $L$ 的值有关：
  • 若 $L \leq 2.5 \times 10^5$，则 $S = 75$。
  • 若 $2.5 \times 10^5 < L \leq 6 \times 10^5$，则 $S = 2 + 70 \times \left(\frac{600\,000 - L}{350\,000}\right)^2$。
  • 否则， $S = 0$。
• 最终你的得分为 $S$。

即，为了获得满分，你最多只能传递长为 $2.5 \times 10^5$ 的二进制串。