405881: GYM102147 C Quantum teleportation

Scientists in an IT company developed a quantum supercomputer. The prototype contains $$$n \times m$$$ quantum processors, arranged in a grid with $$$n$$$ rows and $$$m$$$ columns, both numbered starting from $$$1$$$. We denote the processor in the $$$j$$$-th cell of the $$$i$$$-th row as $$$(i, j)$$$.

After scientists have launched the quantum supercomputer, a failure in the power supply damaged a portion of the processors. Researchers are left with only $$$k$$$ working processors.

A piece of important information is initially in the memory of the processor $$$(1, 1)$$$ and it needs to be transferred to the processor $$$(n, m)$$$, where the output device is located. Transferring information from one processor to another requires quantum teleportation. The peculiarity of quantum teleportation lies in the fact that with increasing distance there is instability, requiring additional energy. Therefore, the transfer of information from the processor $$$(x_i, y_i)$$$ to the processor $$$(x_j, y_j)$$$ requires $$$2^{\max(|x_i - x_j|, |y_i - y_j|)}$$$ units of energy. Scientists want to transfer the information from the processor $$$(1, 1)$$$ to the processor $$$(n, m)$$$, spending the minimum possible amount of energy. They can use only working processors.

Your task is to write a program that, given the positions of working processors, determines how to transfer the data from $$$(1, 1)$$$ to $$$(n, m)$$$, spending the minimum possible amount of energy.

The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ — the number of rows and columns in the grid and the number of processors that survived the power outage ($$$2 \le n, m, k \le 10\,000$$$).

The $$$i$$$-th of the following $$$k$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the row and column number of the $$$i$$$-th working processor ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$).

It is guaranteed that $$$(x_1, y_1) = (1, 1)$$$, $$$(x_k, y_k) = (n, m)$$$. The given $$$k$$$ processors are in different cells of the grid.

The first line of the output should contain an integer $$$L$$$ — the number of processors that will be used in the transmission of the information.

The second line should contain $$$L$$$ integers — the indices of processors in the order in which they will obtain the information. The first index must be $$$1$$$ and the last one must be $$$k$$$.

If there are several ways to achieve the minimum possible total amount of energy spent, you can output any of them.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 21 & 2 \le n, m, k \le 20 & 0 \\ \hline 2 & 13 & 2 \le n, m, k \le 500 & 0, 1 \\ \hline 3 & 33 & 2 \le n, m, k \le 10\,000; x_i \neq x_j; y_i \neq y_j & \\ \hline 4 & 33 & 2 \le n, m, k \le 10\,000 & 0 - 4 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

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