存在一个连通无向简单仙人掌图（cactus graph）$^1$，包含 $N \le 1000$ 个节点和 $M$ 条边。节点的颜色由非负整数（$0$ 到 $1499$）表示。初始时所有节点的颜色均为 $0$。一个确定性无记忆机器人$^2$通过在节点间移动来探索图。它必须至少访问所有节点一次，然后终止。
机器人从图中的某个节点开始，该节点可以是图中的任意节点。在每一步中，它会看到当前节点的颜色以及所有相邻节点的颜色，且顺序对于当前节点是固定的（即再次访问该节点时，即使颜色发生了变化，机器人看到的相邻节点序列也是相同的）。机器人执行以下两种操作之一：
- 决定终止。
- 为当前节点选择一个新颜色（或保持原色），并选择移动到哪个相邻节点。相邻节点由 $0$ 到 $D-1$ 的索引标识，其中 $D$ 是相邻节点的数量。
在第二种情况下，当前节点被重新着色（或保持原色），机器人移动到选定的相邻节点。此过程重复进行，直到机器人终止或达到迭代限制。如果机器人在 $L = 3000$ 步的迭代限制内访问了所有节点并终止，则机器人获胜（否则视为失败）。
你需要为机器人设计一种策略，使其能够解决任何此类仙人掌图上的问题。此外，你应该尽量减少你的方案所使用的不同颜色的数量。在此，颜色 $0$ 始终计为已使用。
$^1$ 连通无向简单仙人掌图是一个连通无向简单图（每个节点均可从其他节点到达；边是双向的；没有自环或重边），其中每条边最多属于一个简单环（简单环是指每个节点最多包含一次的环）。下图是一个示例。
$^2$ 如果机器人的动作仅取决于其当前输入（即它不在步骤之间存储任何数据），并且在给定相同输入时总是选择相同的动作，则称该机器人是确定性且无记忆的。
实现细节
机器人的策略应通过以下函数实现：
std::pair<int, int> navigate(int currColor, std::vector<int> adjColors)该函数接收当前节点的颜色和所有相邻节点的颜色（按顺序）作为参数。它必须返回一个 pair，其第一个元素是当前节点的新颜色，第二个元素是机器人应移动到的相邻节点的索引。如果机器人应该终止，函数应返回 (-1, -1)。
该函数将被反复调用以选择机器人的动作。由于它是确定性的，如果 navigate 之前曾以某些参数被调用过，它将永远不会再以相同的参数被调用；相反，其之前的返回值将被重用。此外，每个测试可能包含 $T \le 5$ 个子任务（不同的图和/或起始位置），它们可能并发运行（即你的程序可能会收到关于不同子任务的交替调用）。最后，对 navigate 的调用可能发生在程序的多次独立执行中（但也可能发生在同一次执行中）。你的程序总执行次数为 $P = 100$。因此，你的程序不应尝试在不同的调用之间传递信息。
数据范围
- $3 \le N \le 1000$
- $0 \le \text{Color} < 1500$
- $L = 3000$
- $T \le 5$
- $P = 100$
子任务
| 子任务 | 分值 | 必选子任务 | $N$ | 附加约束 |
|---|---|---|---|---|
| 0 | 0 | — | $\le 300$ | 示例。 |
| 1 | 6 | — | $\le 300$ | 图是一个环$^1$。 |
| 2 | 7 | — | $\le 300$ | 图是一个星形图$^2$。 |
| 3 | 9 | — | $\le 300$ | 图是一条路径$^3$。 |
| 4 | 16 | 2 - 3 | $\le 300$ | 图是一棵树$^4$。 |
| 5 | 27 | — | $\le 300$ | 所有节点最多有 3 个相邻节点，且机器人起始节点有 1 个相邻节点。 |
| 6 | 28 | 0 - 5 | $\le 300$ | — |
| 7 | 7 | 0 - 6 | — | — |
$^1$ 环图的边为：$(i, (i + 1) \pmod N)$，其中 $0 \le i < N$。 $^2$ 星形图的边为：$(0, i)$，其中 $1 \le i < N$。 $^3$ 路径图的边为：$(i, i + 1)$，其中 $0 \le i < N - 1$。 $^4$ 树是没有环的图。
评分
你在某个子任务中获得的分数比例 $S$ 取决于 $C$ —— 即你的方案在该子任务或任何其他必需子任务的任何测试中使用的不同颜色的最大数量（包括颜色 $0$）：
- 如果你的方案在任何子任务上失败，则 $S = 0$。
- 如果 $C \le 4$，则 $S = 1.0$。
- 如果 $4 < C \le 8$，则 $S = 1.0 - 0.6 \frac{C-4}{4}$。
- 如果 $8 < C \le 21$，则 $S = 0.4 \frac{8}{C}$。
- 如果 $C > 21$，则 $S = 0.15$。
样例
考虑题目描述中图片所示的示例图，其中 $N = 7, M = 8$，边为 $(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2), (3, 5)$ 和 $(2, 6)$。此外，由于节点邻接列表中元素的顺序很重要，我们在下表中给出：
| 节点 | 相邻节点 |
|---|---|
| 0 | 2, 1 |
| 1 | 2, 0 |
| 2 | 0, 3, 4, 6, 1 |
| 3 | 4, 5, 2 |
| 4 | 2, 3 |
| 5 | 3 |
| 6 | 2 |
假设机器人从节点 $5$ 开始。以下是一种可能的（不成功的）交互序列：
| # | 颜色 | 节点 | navigate 调用 |
返回值 |
|---|---|---|---|---|
| 1 | 0, 0, 0, 0, 0, 0, 0 | 5 | navigate(0, {0}) |
{1, 0} |
| 2 | 0, 0, 0, 0, 0, 1, 0 | 3 | navigate(0, {0, 1, 0}) |
{4, 2} |
| 3 | 0, 0, 0, 4, 0, 1, 0 | 2 | navigate(0, {0, 4, 0, 0, 0}) |
{0, 3} |
| 4 | 0, 0, 0, 4, 0, 1, 0 | 6 | navigate(0, {0}) |
{1, 0} |
| 5 | 0, 0, 0, 4, 0, 1, 1 | 2 | navigate(0, {0, 4, 0, 1, 0}) |
{8, 0} |
| 6 | 0, 0, 8, 4, 0, 1, 1 | 0 | navigate(0, {8, 0}) |
{3, 0} |
| 7 | 3, 0, 8, 4, 0, 1, 1 | 2 | navigate(8, {3, 4, 0, 1, 0}) |
{2, 2} |
| 8 | 3, 0, 2, 4, 0, 1, 1 | 4 | navigate(0, {2, 4}) |
{1, 1} |
| 9 | 3, 0, 2, 4, 1, 1, 1 | 3 | navigate(4, {1, 1, 2}) |
{-1, -1} |
在此，机器人总共使用了 $6$ 种不同的颜色：$0, 1, 2, 3, 4$ 和 $8$（注意，即使机器人从未返回过颜色 $0$，颜色 $0$ 也计为已使用，因为所有节点初始颜色均为 $0$）。机器人运行了 $9$ 次迭代后终止。然而，它失败了，因为它在未访问节点 $1$ 的情况下就终止了。
说明
样例评测程序不会多次运行你的程序，因此对 navigate 的所有调用都将在程序的同一次执行中进行。
输入格式如下：首先读取 $T$（子任务数量）。然后对于每个子任务： 第 $1$ 行：三个整数 —— $N, M$ 和 $S$（机器人的起始节点）； 第 $2+i$ 行（对于 $0 \le i < M$）：两个整数 —— $A_i$ 和 $B_i$，表示边 $i$ 连接的两个节点（$0 \le A_i, B_i < N$）。
样例评测程序随后将打印出你的方案所使用的不同颜色的数量以及它在终止前所需的迭代次数。或者，如果你的方案失败，它将打印一条错误消息。
默认情况下，样例评测程序会打印关于机器人在每次迭代中看到的内容和所做动作的详细信息。你可以通过将 DEBUG 的值从 true 改为 false 来禁用此功能。