{"problem":{"name":"[ROI 2018] Quantum teleportation","description":{"content":"在一个平面直角坐标系上有编号为 $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 通","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9289"},"statements":[{"statement_type":"Markdown","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，至少需要多久，并给出一组方案。\n\n## Input\n\n第一行三个整数 $n,m,k$。\n\n以下 $k$ 行，每行两个整数 $x_i,y_i$。\n\n## Output\n\n第一行一个整数 $L$，表示最快的方案中要经过多少块 CPU。\n\n第二行 $L$ 个整数，表示依次经过的 CPU。\n\n如果存在多组路径使耗时最少，输出任意一种即可。\n\n[samples]\n\n## Background\n\n译自 [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))。 \n\n## Note\n\n对于所有的数据，$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$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9289","tags":["2018","Special Judge","ROI（俄罗斯）"],"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 "]],"created_at":"2026-03-03 11:09:25"}}