{"raw_statement":[{"iden":"background","content":"译自 [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))。 "},{"iden":"statement","content":"在一个平面直角坐标系上有编号为 $1\\dots k$ 的 $k$ 块 CPU。\n\n每块 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$。\n\n$i$ 号 CPU 通过总线将一笔数据传输到 $j$ 号 CPU 的耗时为 ${2^{\\max(|x_{{i}}-x_{{j}}|,|y_{{i}}-y_{{j}}|)}}$ 个单位时间。\n\n试求：要将数据从 $1$ 号 CPU 传送到 $k$ 号 CPU，至少需要多久，并给出一组方案。"},{"iden":"input","content":"第一行三个整数 $n,m,k$。\n\n以下 $k$ 行，每行两个整数 $x_i,y_i$。"},{"iden":"output","content":"第一行一个整数 $L$，表示最快的方案中要经过多少块 CPU。\n\n第二行 $L$ 个整数，表示依次经过的 CPU。\n\n如果存在多组路径使耗时最少，输出任意一种即可。"},{"iden":"note","content":"对于所有的数据，$2 \\leq n,m,k \\leq 10000$。\n\n| 子任务编号 | $n,m,k$ | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $2 \\leq n,m,k \\leq 20$ | 无 |\n| $2$ | $2 \\leq n,m,k \\leq 500$ | 无 |\n| $3$ | $2 \\leq n,m,k \\leq 10000$ | 每行、每列只有一个 CPU |\n| $4$ | $2 \\leq n,m,k \\leq 10000$ | 无 |\n"}],"translated_statement":null,"sample_group":[["4 5 3\n1 1\n2 3\n4 5","3\n1 2 3"],["5 6 9\n1 1\n4 3\n4 6\n2 5\n3 1\n3 3\n3 6\n5 4\n5 6","5\n1 6 2 8 9 "]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}