P9289 [ROI 2018] Quantum teleportation

译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Квантовая телепортация ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf)([Quantum teleportation](https://codeforces.com/gym/102147/problem/C))。

在一个平面直角坐标系上有编号为 $1\dots k$ 的 $k$ 块 CPU。 每块 CPU 的位置可以用平面上的坐标来表示。$1$ 号 CPU 位于 $(1,1)$，$k$ 号 CPU 位于 $(n,m)$。保证所有 CPU 均位于整点上，且对于每块 CPU 的坐标 $(x_i, y_i)$，保证 $1 \le x_i \le n, 1 \le y_i \le m$。 $i$ 号 CPU 通过总线将一笔数据传输到 $j$ 号 CPU 的耗时为 ${2^{\max(|x_{{i}}-x_{{j}}|,|y_{{i}}-y_{{j}}|)}}$ 个单位时间。 试求：要将数据从 $1$ 号 CPU 传送到 $k$ 号 CPU，至少需要多久，并给出一组方案。

第一行三个整数 $n,m,k$。 以下 $k$ 行，每行两个整数 $x_i,y_i$。

第一行一个整数 $L$，表示最快的方案中要经过多少块 CPU。 第二行 $L$ 个整数，表示依次经过的 CPU。 如果存在多组路径使耗时最少，输出任意一种即可。

对于所有的数据，$2 \leq n,m,k \leq 10000$。 | 子任务编号 | $n,m,k$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $2 \leq n,m,k \leq 20$ | 无 | | $2$ | $2 \leq n,m,k \leq 500$ | 无 | | $3$ | $2 \leq n,m,k \leq 10000$ | 每行、每列只有一个 CPU | | $4$ | $2 \leq n,m,k \leq 10000$ | 无 |