题目描述

译自 ROI 2018 Day1 T4. Квантовая телепортация (Quantum teleportation)

在一个平面直角坐标系上有编号为 $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^{\large\max(|x_{\normalsize{i}}-x_{\normalsize{j}}|,|y_{\normalsize{i}}-y_{\normalsize{j}}|)}}$ 个单位时间。

试求：要将数据从 $1$ 号 CPU 传送到 $k$ 号 CPU，至少需要多久，并给出一组方案。

输入格式

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

输出格式

第一行一个整数 $L$，表示最快的方案中要经过多少块 CPU。
第二行 $L$ 个整数，表示依次经过的 CPU。

如果存在多组路径使耗时最少，输出任意一种即可。

4 5 3
1 1
2 3
4 5

3
1 2 3

5 6 9
1 1
4 3
4 6
2 5
3 1
3 3
3 6
5 4
5 6

5
1 6 2 8 9

数据范围与提示