量子 teleportation（Quantum teleportation）

题目描述

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

在一个平面直角坐标系上有编号为 1 到 k 的 k 块 CPU。

每块 CPU 的位置可以用平面上的坐标来表示。1 号 CPU 位于 (1,1)，k 号 CPU 位于 (n,m)。保证所有 CPU 均位于整点上，且对于每块 CPU 的坐标 (x_i, y_i)，满足 1 ≤ x_i ≤ n，1 ≤ y_i ≤ m。

i 号 CPU 通过总线将一笔数据传输到 j 号 CPU 的耗时为 (2^{\max(|x_i - x_j|,|y_i - y_j|)}) 个单位时间。

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

输入格式

$第一行三个整数 n,m,k。$以下 k 行，每行两个整数 x,y，依次表示 1 号到 k 号 CPU 的坐标。

输出格式

$第一行一个整数 L，表示最快的方案中要经过多少块 CPU。$第二行 L 个整数，表示依次经过的 CPU 的编号（从 1 号到 k 号）。

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

样例 1

输入

4 5 3
1 1
2 3
4 5

输出

3
1 2 3

样例 2

输入

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

数据范围与提示