20449번 - Квантовая телепортация 서브태스크스페셜 저지다국어

문제

Ученые в 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$.

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

제한

서브태스크

힌트