시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB222100.000%

문제

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

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

예제 입력 1

4 5 3
1 1
2 3
4 5

예제 출력 1

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

예제 출력 2

5
1 6 2 8 9