在俄罗斯的许多地方，冬季都会下雪。俄罗斯有 $N$ 个城市，编号从 $0$ 到 $N-1$。俄罗斯有 $N-1$ 条道路，编号从 $0$ 到 $N-2$。道路 $i$ ($0 \le i \le N-2$) 双向连接两个不同的城市 $A_i$ 和 $B_i$ ($0 \le A_i < B_i \le N-1$)。俄罗斯任意两个不同的城市之间，都可以通过若干条道路往来。

每条道路的降雪情况随日期而变化。在任何一天，每条道路的降雪情况要么是“有雪”，要么是“无雪”。一天之内降雪情况不会发生变化。

Anya 和 Boris 在俄罗斯交通局工作。Anya 负责道路信息管理部门，Boris 负责回答市民的咨询。市民的咨询内容是：从俄罗斯首都城市 $0$ 到其他某个城市，最少需要经过多少条有雪的道路。Boris 通常在收到咨询后，与 Anya 进行交流，然后回答市民。

此次，俄罗斯将举办为期 $Q$ 天的编程竞赛世界大会。大会期间，通信线路拥堵，预计 Anya 和 Boris 难以直接交流。因此，Anya 和 Boris 决定采用以下方式进行交流：

• Anya 在每天开始时接收当天的降雪信息，并将数据发送到中继服务器。
• Boris 在收到市民的咨询后，通过与中继服务器交互来回答。

但是，Anya 和 Boris 的交流有以下限制：

• 中继服务器的容量为 $L = 1000$ 比特。Anya 最多只能在中继服务器中存储 $L$ 比特的信息。
• 中继服务器中存储的数据在每天开始时全部初始化为 $0$。
• Boris 通过与中继服务器进行一次交互，可以读取指定的 $1$ 比特信息。
• 为了回答咨询，Boris 每次咨询最多只能与中继服务器交互 $20$ 次。

作为交通局长的熟人，你需要构思 Anya 和 Boris 的策略。

实现细节

你必须使用同一种编程语言提交两个文件。

第一个文件名为 Anya.c 或 Anya.cpp。该文件实现了 Anya 的策略，必须实现以下两个例程。程序必须包含 Anyalib.h。

• void InitAnya(int N, int A[], int B[]) 该函数在每个测试用例中仅被调用一次。

  • 参数 $N$ 表示城市数量。
  • 参数 $A[]$ 和 $B[]$ 分别是长度为 $N-1$ 的数组，表示道路连接信息。元素 $A[i]$ 和 $B[i]$ ($0 \le i \le N-2$) 是整数，表示道路 $i$ 双向连接城市 $A[i]$ 和 $B[i]$，满足 $0 \le A[i] < B[i] \le N-1$。

• void Anya(int C[]) 该函数在 InitAnya 被调用后，会被调用 $Q$ 次。该函数对应于每天开始时道路降雪信息更新后，Anya 决定存储在中继服务器中的比特序列。

  • 参数 $C[]$ 是长度为 $N-1$ 的数组，表示道路降雪信息。元素 $C[i]$ ($0 \le i \le N-2$) 是 $0$ 或 $1$ 的整数，若 $C[i] = 1$ 表示道路 $i$ 有雪，若 $C[i] = 0$ 表示道路 $i$ 无雪。

在函数 Anya 中，可以调用以下函数：

• void Save(int place, int bit) 该函数表示 Anya 向中继服务器保存比特的操作。
  • 参数 place 表示写入比特的位置。place 必须是 $0$ 到 $L-1$ 之间的整数。若指定范围外的值，将被判定为不正确 [1]。此外，在函数 Anya 的每次调用中，不能对同一个 place 调用两次以上。若对同一个参数调用两次，将被判定为不正确 [2]。
  • 参数 bit 是表示要写入比特的整数，必须是 $0$ 或 $1$。若指定其他值，将被判定为不正确 [3]。

Save 调用后，中继服务器第 place 位的内容变为 bit。若 Save 调用被判定为不正确，程序将立即终止。

在函数 Anya 被调用前，中继服务器的所有比特位必定初始化为 $0$。也就是说，在函数 Anya 结束时，未通过 Save 函数进行保存操作的位置上写入的是 $0$。

第二个文件名为 Boris.c 或 Boris.cpp。该文件实现了 Boris 的策略，必须实现以下两个例程。程序必须包含 Borislib.h。

• void InitBoris(int N, int A[], int B[]) 该函数在每个测试用例中仅被调用一次。

  • 参数 $N$ 表示城市数量。
  • 参数 $A[]$ 和 $B[]$ 分别是长度为 $N-1$ 的数组，表示道路连接信息。元素 $A[i]$ 和 $B[i]$ ($0 \le i \le N-2$) 是整数，表示道路 $i$ 双向连接城市 $A[i]$ 和 $B[i]$，满足 $0 \le A[i] < B[i] \le N-1$。

• int Boris(int city) 该函数在 InitBoris 被调用后会被调用多次。该函数对应于 Boris 对市民咨询的行动。

  • 参数 city 表示市民的咨询。city 是 $1$ 到 $N-1$ 之间的整数。这表示市民正在咨询从城市 $0$ 到城市 city 移动时，最少需要经过多少条有雪的道路。
  • 函数 Boris 必须返回一个 $0$ 到 $N-1$ 之间的整数，作为对市民咨询的回答。若返回该范围外的整数，将被判定为不正确 [4]。若回答不正确，将被判定为不正确 [7]。

在函数 Boris 中，可以调用以下函数：

• int Ask(int place) 该函数表示 Boris 从中继服务器读取比特的操作。
  • 参数 place 表示读取比特的位置。place 必须是 $0$ 到 $L-1$ 之间的整数。若指定范围外的值，将被判定为不正确 [5]。 函数 Ask 的返回值是表示中继服务器第 place 位内容的整数，为 $0$ 或 $1$。此外，函数 Ask 在函数 Boris 的每次调用中，最多只能调用 $20$ 次。若调用超过 $20$ 次，将被判定为不正确 [6]。

若 Ask 调用被判定为不正确，程序将立即终止。

评分步骤

评分按以下步骤进行。若被判定为不正确，程序将立即终止。

(1) 为了提供道路信息，InitAnya 和 InitBoris 将按此顺序各被调用一次。 (2) 对于 $i = 1, \dots, Q$，依次执行以下操作： (a) 调用一次函数 Anya。这对应于每天开始时道路降雪信息更新后，Anya 决定存储在中继服务器中的比特序列。 (b) 调用 $D_i$ 次函数 Boris。$D_i$ 是第 $i$ 天市民咨询的次数。其中第 $j$ 次（$1 \le j \le D_i$）调用的参数是 $R_{ij}$ ($1 \le R_{ij} \le N-1$)。在第 $j$ 次调用中，如果函数 Boris 的返回值与从城市 $0$ 到城市 $R_{ij}$ 移动所需经过的有雪道路的最少条数不一致，则判定为不正确。 (3) 如果从未被判定为不正确，则判定为正确。

重要注意事项

• 执行时间测量和内存使用测量对象是“评分步骤”中的步骤 (1) 和 (2)。如果是正确的情况，在步骤 (2) 中，Anya 总共被调用 $Q$ 次，Boris 总共被调用 $D_1 + \dots + D_Q$ 次。
• Anya 和 Boris 无法获知 $D_1, \dots, D_Q$ 的值。
• 函数 Boris 不会被告知 Anya 在何时更新了中继服务器中存储的数据。
• 可以自由实现其他例程或声明全局变量以供内部使用。但是，由于提交的两个程序将与评分程序链接在一起成为一个可执行文件，因此必须将每个文件中的所有全局变量和内部例程（InitAnya, Anya, InitBoris, Boris 除外）声明为 static，以避免与其他文件冲突。在评分时，该程序将作为 Anya 侧和 Boris 侧两个进程运行，因此 Anya 侧和 Boris 侧无法共享程序中的全局变量。
• 你的提交不得以任何方式与标准输入、标准输出或其他文件进行交互。

编译与运行方法

用于测试所编写程序的评分程序示例包含在可从竞赛网站下载的压缩包中。该压缩包还包含必须提交的文件示例。

评分程序示例由一个文件组成，即 grader.c 或 grader.cpp。当创建的程序为 Anya.c 和 Boris.c，或 Anya.cpp 和 Boris.cpp 时，可以通过以下命令测试程序：

• C 语言： gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm
• C++ 语言： g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

如果编译成功，将生成名为 grader 的可执行文件。 请注意，实际的评分程序与评分程序示例不同。评分程序示例作为单个进程启动。该程序从标准输入读取输入，并将结果输出到标准输出。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 500$
• $1 \le Q \le 500$
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$)
• $1 \le D_j$ ($1 \le j \le Q$)
• $D_1 + \dots + D_Q \le 500$
• 任意两个不同的城市之间都可以通过若干条道路往来。

子任务

子任务 1 [15 分]

• 满足 $N \le 20$。

子任务 2 [5 分]

• 满足 $N \le 100$。

子任务 3 [35 分]

满足以下条件： $A_i = i$ ($0 \le i \le N-2$) $B_i = i + 1$ ($0 \le i \le N-2$)

子任务 4 [45 分]

• 无额外限制。

样例

输入格式 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

输出格式 1

1 0 2
0

说明

此样例展示了评分程序示例的输入格式及对应的函数调用序列。在实际运行中，InitAnya、InitBoris 以及 Anya 的调用参数如下表所示：