题目背景

译自 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^{\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。

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

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 

提示

对于所有的数据，$2 \leq n,m,k \leq 10000$。