C. Квантовая телепортация
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ученые в IT-компании разработали квантовый суперкомпьютер. Опытный образец, разработанный учеными, содержит $$$n \times m$$$ квантовых процессоров, организованных в виде сетки из $$$n$$$ строк и $$$m$$$ столбцов. Обозначим процессор в $$$j$$$-й ячейке $$$i$$$-й строки как $$$(i, j)$$$.

Ученые запустили квантовый суперкомпьютер, однако после окончания вычислений произошел сбой в электропитании, из-за чего часть процессоров оказалась повреждена. В распоряжении исследователей осталось всего лишь $$$k$$$ уцелевших процессоров.

Результат вычислений находится в памяти процессора $$$(1, 1)$$$, а устройство вывода подключено к процессору $$$(n, m)$$$. Для передачи информации от одного процессора к другому используется квантовая телепортация. Особенность квантовой телепортации заключается в том, что с увеличением расстояния возникает нестабильность, требующая дополнительной энергии. Поэтому чтобы обеспечить перенос информации от процессора $$$(x_i, y_i)$$$ к процессору $$$(x_j, y_j)$$$ требуется $$$2^{\max(|x_i - x_j|, |y_i - y_j|)}$$$ единиц энергии. Ученые хотят перенести информацию с процессора $$$(1, 1)$$$ на процессор $$$(n, m)$$$, затратив минимальное количество энергии. При этом можно использовать в качестве промежуточных другие уцелевшие процессоры. Использовать поврежденные процессоры нельзя.

Требуется написать программу, которая по описанию уцелевших процессоров определяет, каким образом необходимо передавать данные между процессорами, чтобы перенести информацию из процессора $$$(1, 1)$$$ в процессор $$$(n, m)$$$, потратив минимальное суммарное количество энергии.

Входные данные

В первой строке входных данных находятся три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество строк и столбцов в сетке и количество оставшихся невредимыми после отключения электричества процессоров ($$$2 \le n, m, k \le 10\,000$$$).

Далее следуют $$$k$$$ строк, в $$$i$$$-й из которых содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ —номер строки и столбца $$$i$$$-го уцелевшего процессора ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$).

Гарантируется, что $$$(x_1, y_1) = (1, 1)$$$, $$$(x_k, y_k) = (n, m)$$$. Все процессоры находятся в разных ячейках сетки.

Выходные данные

Первая строка выходных данных должна содержать число $$$L$$$ — количество процессоров, которые будут использованы при передаче информации.

Вторая строка должна содержать $$$L$$$ чисел — номера уцелевших процессоров в том порядке, в котором они будут получать информацию. Первым должен быть выведен процессор номер $$$1$$$, а последним — процессор номер $$$k$$$.

Если вариантов передачи информации, минимизирующих затраченную энергию, несколько, то можно вывести любой из них.

Система оценки

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \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}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.

Примеры
Входные данные
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