Marcel 开始进行速通（speedrun），希望能创造新的世界纪录（WR）。遗憾的是，他无法掌握新发现的技巧，因此他必须找到一种方法来获得不公平的优势。

他试图精通的游戏名为《Tree Souls III》，他正尝试在 full-tree% 类别中获得 WR。

顾名思义，游戏发生在一棵树上（即一个有 $N$ 个顶点、编号从 $1$ 到 $N$ 且有 $N-1$ 条边，且无环的图）。

游戏规则如下：角色被放置在树内的一个任意节点上。他可以选择一个整数 $x$，并尝试从他所在的节点走到节点 $x$。如果 $x$ 与他当前所在的节点之间有一条边，他就会移动到 $x$，否则什么也不会发生。如果他至少访问过每个节点一次，他的速通即为有效。

现在，作弊的部分来了：由于他不知道“边传送故障”（edge-teleportation-glitch），他打算为他的世界设置种子，因此在开始速通之前，他会知道树的结构。如果他只是记住了树的结构，那么他作弊的意图就太明显了，他会立即被速通社区封禁，因此他只是在每个节点上放置一些提示（通过篡改代码）。提示是一个长度为 $l$ 的二进制字符串（每个节点上的提示长度 $l$ 相同）。当他位于某个节点时，他可以读取分配给当前节点的提示。

交互

这是一个双重交互问题！

你的代码将被运行两次，一次用于第一次交互（提示设置阶段），另一次用于第二次交互（速通阶段）。

你必须实现以下函数（且不能实现 main 函数）：

void assignHints(int subtask, int N, int A[], int B[]);
void speedrun(int subtask, int N, int start);

使用以下可调用函数：

void setHintLen(int l);
void setHint(int i, int j, bool b);
int getLength();
bool getHint(int j);
bool goTo(int x);

提示设置阶段。这是你代码的第一次运行。在此阶段，评测系统的代码将恰好调用一次 assignHints 函数。它将传入子任务索引 subtask 和 $N$ 作为参数，并通过 A 和 B 传入树的边：对于每个 $i = 1, \dots, N-1$，在 $A[i]$ 和 $B[i]$ 之间有一条边。然后，你必须恰好调用一次 setHintLen 函数，并将你决定使用的提示长度作为参数传入。调用 setHintLen 后，你可以多次调用 setHint(i, j, b) 函数。这会将节点 $i$ 的提示的第 $j$ 位设置为 $b$。位索引从 $1$ 到 $l$。提示初始时全部填充为零。在此阶段，你不得调用 getLength、getHint 或 goTo 函数。当你完成提示分配后，你的代码应从 assignHints 返回。

速通阶段。这是你代码的第二次运行。在此阶段，评测系统的代码将恰好调用一次 speedrun(subtask, N, start) 函数，告知你速通者开始的节点 start 以及 $N$ 的值。此外，你还会通过参数 subtask 接收子任务的索引。然后，你可以调用 getLength() 函数，它返回你在第一阶段设置的提示长度 $l$；调用 getHint(j) 函数，它告诉你当前所在节点的提示的第 $j$ 位；以及 goTo 函数。如果传给 goTo 的参数是与当前节点有边相连的节点的索引，则该函数返回 true 并且你移动到该节点。否则，它返回 false 并且你不会离开当前节点。在此阶段，你不得调用 setHint 或 setHintLen 函数。在访问树中所有节点后，你的代码应最终从 speedrun 函数返回。

数据范围

• $1 \le N \le 1\,000$
• 令 $Q$ 为 goTo 返回 false 的调用次数。以下概述了为了在每个子任务中获得分数必须遵守的 $l$ 和 $Q$ 的限制。

子任务 1（21 分）

• $l \le N$
• $Q \le 2000$
• 如果所有测试点均正确解决，则该子任务得 21 分，否则得 0 分。

子任务 2（8 分）

• $l \le 20$
• $Q \le 2000$
• 树是一颗星形图；即存在一个节点 $x$ ($1 \le x \le N$)，它与所有其他节点相连。
• 如果所有测试点均正确解决，则该子任务得 8 分，否则得 0 分。

子任务 3（19 分）

• $l \le 20$
• $Q \le 2000$
• 每个节点的度数最多为 2。
• 如果所有测试点均正确解决，则该子任务得 19 分，否则得 0 分。

子任务 4（12 分）

• $l \le 316$
• $Q \le 32000$
• 如果所有测试点均正确解决，则该子任务得 12 分，否则得 0 分。

子任务 5（40 分）

• $Q \le 2000$
• 每个测试点的得分 $s$ 计算如下：如果 $l > 40$，则 $s = 0$。如果 $l \le 20$，则 $s = 40$。否则，$s = 60 - l$。也就是说，如果 $l = 40$，你将获得该测试点一半的分数；如果 $l \le 20$，你将获得该测试点的满分。子任务的得分为该子任务中所有测试点得分 $s$ 的最小值。

样例

在第一次交互（提示设置阶段），选手的函数将被调用如下：

assignHints(
/* subtask = */ 1,
/* N = */ 5,
/* A = */ {-, 1, 2, 3, 3},
/* B = */ {-, 2, 3, 4, 5});

该函数反过来可以选择设置 $l = 2$：

setHintLen(/* l = */ 2);

然后将所有提示位设为 0，除了节点 2 的第 1 位设为 1：

setHint(
/* i = */ 2,
/* j = */ 1,
/* b = */ 1);

然后它退出。选手程序的第一个实例现在将终止，因此该程序存储在内存中的任何数据都将丢失。此时，除了节点 2 的提示为 "10" 外，每个节点的提示均为 "00"。

在第二次交互（速通阶段），选手的函数将被调用：

speedrun(
/* subtask = */ 1,
/* N = */ 5,
/* start = */ 1);

作为回应，该函数开始速通这棵树：

getLength(); // = 2
getHint(1); // = 0
getHint(2); // = 0
goTo(2); // = true
getHint(1); // = 1
getHint(2); // = 0

此时，你最初在节点 1，发现 $l = 2$ 且节点 1 的提示是 "00"，然后成功移动到节点 2 并发现节点 2 的提示是 "10"。执行可以继续如下：

goTo(2); // = false (你不能从节点 2 回到它自身)
goTo(5); // = false (从节点 2 到节点 5 没有边)
goTo(3); // = true
goTo(4); // = true
goTo(3); // = true
goTo(5); // = true

此时所有节点都已到达，因此 speedrun 函数可以退出。$Q = 2$，因为有 2 次 goTo 调用返回了 false。