Xedef 快递公司在数个城市之间提供航空包裹运输服务。其中一些城市是 Xedef 的枢纽（hubs），那里建有特殊的处理设施。Xedef 的每架飞机在某一对城市之间往返飞行，根据需要双向运送包裹。

为了将包裹从一个城市运送到另一个城市，包裹必须通过一系列的单次航程（hops）进行传送，其中每次航程都在由一架飞机服务的两个城市之间进行。此外，该传送序列必须包含至少一个 Xedef 的枢纽。

为了便于路由，Xedef 希望在每个包裹的邮寄标签上编码从每个城市到每个枢纽的最短航程序列的长度。（从一个枢纽到其自身的最短序列长度为零。）显然，需要对这些信息进行紧凑的表示。

你需要实现两个函数：encode(N,H,P,A,B) 和 decode(N,H)。$N$ 是城市的数量，$H$ 是枢纽的数量。假设城市从 $0$ 到 $N-1$ 编号，且枢纽是编号在 $0$ 到 $H-1$ 之间的城市。进一步假设 $N \le 1000$ 且 $H \le 36$。$P$ 是由飞机连接的城市对的数量。所有（无序）城市对都是两两不同的。$A$ 和 $B$ 是大小为 $P$ 的数组，使得第一对连接的城市为 $(A[0], B[0])$，第二对为 $(A[1], B[1])$，依此类推。

encode 必须计算一个位（bit）序列，decode 可以通过该序列确定从每个城市到每个枢纽的航程数。encode 将通过一系列对 encode_bit(b) 的调用将位序列传输给评测服务器，其中 $b$ 为 $0$ 或 $1$。decode 将通过调用 decode_bit 从评测服务器接收该位序列。第 $i$ 次调用 decode_bit 将返回第 $i$ 次调用 encode_bit(b) 时传入的 $b$ 值。注意，你必须确保 decode 调用 decode_bit 的次数在任何时候都最多等于 encode 之前调用 encode_bit(b) 的次数。

在解码出航程数后，decode 必须对每个枢纽 $h$ 和每个城市 $c$（包括每个枢纽自身，即也包括 $c=h$ 的情况）调用 hops(h,c,d)，给出在 $h$ 和 $c$之间运送包裹所需的最少航程数 $d$。也就是说，必须进行 $N \times H$ 次对 hops(h,c,d) 的调用。调用的顺序无关紧要。保证在任意枢纽和任意城市之间总是可以运送包裹。

说明：encode 和 decode 只能通过指定的接口进行通信。禁止使用共享变量、文件访问和网络访问。在 C 或 C++ 中，你可以将持久变量声明为 static 以保留 encode 或 decode 的信息，同时防止它们被共享。在 Pascal 中，你可以在解决方案文件的 implementation 部分声明持久变量。

样例

作为示例，考虑右侧的图。它显示了由七架飞机（$P=7$）连接的五个城市（$N=5$）。城市 0、1 和 2 是枢纽（$H=3$）。在枢纽 0 和城市 3 之间运送包裹需要 1 次航程，而在枢纽 2 和城市 3 之间运送包裹需要 2 次航程。此示例的数据在 grader.in.1 中。

下表中的各项是 decode 必须通过调用 hops(h,c,d) 交付的所有 $d$ 值：

子任务

子任务 1 [25 points]

encode 调用的 encode_bit(b) 次数不能超过 $16\,000\,000$ 次。

子任务 2 [25 points]

encode 调用的 encode_bit(b) 次数不能超过 $360\,000$ 次。

子任务 3 [25 points]

encode 调用的 encode_bit(b) 次数不能超过 $80\,000$ 次。

子任务 4 [25 points]

encode 调用的 encode_bit(b) 次数不能超过 $70\,000$ 次。

实现细节

• 实现文件夹：/home/ioi2010-contestant/saveit/

• 需要由选手实现的文件：

  • encoder.c 或 encoder.cpp 或 encoder.pas
  • decoder.c 或 decoder.cpp 或 decoder.pas

• 选手接口：

  • encoder.h 或 encoder.pas
  • decoder.h 或 decoder.pas

• 交互器接口：grader.h 或 graderlib.pas

• 样例交互器：grader.c 或 grader.cpp 或 grader.pas 以及 graderlib.pas

• 样例交互器输入：grader.in.1、grader.in.2 等。

  • 注意：每个文件的第一行包含 $N$、$P$、$H$。接下来的 $P$ 行包含城市对 $A[0]\ B[0]$，$A[1]\ B[1]$ 等。接下来的 $H \times N$ 行包含从每个枢纽到每个城市（包括其自身和所有其他枢纽）的航程数；也就是说，从枢纽 $i$ 到城市 $j$ 的航程数位于这些行中的第 $i \times N + j + 1$ 行。

• 样例交互器输入的预期输出：

  • 如果子任务 1 的实现正确，输出将包含 OK 1
  • 如果子任务 2 的实现正确，输出将包含 OK 2
  • 如果子任务 3 的实现正确，输出将包含 OK 3
  • 如果子任务 4 的实现正确，输出将包含 OK 4

• 编译与运行（命令行）：runc grader.c 或 runc grader.cpp 或 runc grader.pas

• 编译与运行（gedit 插件）：在编辑任何实现文件时，按下 Control-R。

• 提交（命令行）：submit grader.c 或 submit grader.cpp 或 submit grader.pas

• 提交（gedit 插件）：在编辑任何实现文件或交互器文件时，按下 Control-J。