양자 텔레포테이션

IT 회사의 연구진이 양자 슈퍼컴퓨터를 개발했다. 시제품은 $n$개의 행과 $m$개의 열로 이루어진 격자 모양이며, 양자 프로세서는 모두 $n \times m$개이다. $i$행 $j$열의 프로세서는 $(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)$으로 옮기려 한다. 중간에는 살아남은 다른 프로세서를 거쳐 갈 수 있다. 손상된 프로세서는 사용할 수 없다.

첫 줄에 정수 $n$, $m$, $k$가 주어진다. 각각 격자의 행 수, 열 수, 살아남은 프로세서의 수이다 ($2 \le n, m, k \le 10000$).

이어지는 $k$개의 줄 중 $i$번째 줄에는 $i$번째 살아남은 프로세서의 행 번호 $x_i$와 열 번호 $y_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$여야 한다.

에너지를 최소로 하는 전송 방법이 여럿이면 그중 아무것이나 출력해도 된다.