Background

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

Problem Description

On a 2D Cartesian coordinate plane, there are $k$ CPUs numbered $1 \dots k$.

The position of each CPU can be represented by coordinates on the plane. CPU $1$ is located at $(1,1)$, and CPU $k$ is located at $(n,m)$. It is guaranteed that all CPUs are on integer grid points, and for each CPU with coordinates $(x_i, y_i)$, it holds that $1 \le x_i \le n$ and $1 \le y_i \le m$.

The time for CPU $i$ to transmit a piece of data to CPU $j$ via the bus is ${2^{\max(|x_{{i}}-x_{{j}}|,|y_{{i}}-y_{{j}}|)}}$ time units.

Find the minimum time needed to send the data from CPU $1$ to CPU $k$, and output one valid plan.

Input Format

The first line contains three integers $n,m,k$.

The next $k$ lines each contain two integers $x_i,y_i$.

Output Format

The first line contains an integer $L$, which denotes how many CPUs are visited in the fastest plan.

The second line contains $L$ integers, denoting the CPUs visited in order.

If there are multiple paths with the minimum time, output any one of them.

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 

Hint

For all testdata, $2 \leq n,m,k \leq 10000$.

Constraints

Translated by ChatGPT 5