28401번 - 격자 속의 직선 경로

문제

현대오토에버는 AI, 로보틱스, IoT, 빅데이터 등 ICT 기술을 기존 생산 공정에 적용하는 스마트 팩토리를 구축하고 있다. 현대오토에버에 다니는 대현이는 새로 구축하는 스마트 팩토리 기술을 적용한 공장의 이동 동선을 최적화하는 일을 하고 있다.

대현이는 가상현실에 실제 공장을 동일하게 구현하는 디지털 트윈 기술을 바탕으로 실제 공장 내에서의 이동을 시뮬레이션해 보고자 한다. 새로 구축하는 공장은 가상 현실 내에서 정사각형 구역 $R\times C$개가 $R$행 $C$열로 붙어 있는 직사각형 격자 형태로 표현된다. 이 중 일부 구역은 이미 설비가 설치되어 있어 내부와 경계를 지나갈 수 없다.

대현이는 1ドル$행 1ドル$열의 구역에서 생산된 부품을 $R$행 $C$열의 구역으로 이동시키고자 한다. 직선 방향으로 이동하는 것이 효율적인 만큼, 대현이는 1ドル$행 1ドル$열 구역 내부 혹은 경계의 어떤 지점에서 $R$행 $C$열 구역 내부 혹은 경계의 어떤 지점으로 부품을 이동시킬 수 있는 직선 경로가 있는지 궁금하다. 대현이를 도와주자.

입력

첫 번째 줄에 격자의 행과 열의 개수를 나타내는 $R$과 $C,ドル 그리고 설비가 설치된 구역의 개수 $K$ 가 주어진다. $(2\leq R,C\leq 1,円 000;$ 1ドル\leq K\leq 100,円 000)$

다음 줄부터 $K$ 개의 줄에 걸쳐서 설비가 설치된 구역의 행 번호 $r$과 열 번호 $c$가 각 줄에 하나씩 주어진다. $(1\leq r\leq R;$ 1ドル\leq c\leq C)$ 1ドル$행 1ドル$열이나 $R$행 $C$열은 주어지지 않으며, 설비가 설치된 구역의 좌표는 서로 다르다.

출력

문제의 조건을 만족하는 직선 경로가 있으면 1ドル,ドル 아니면 0ドル$을 출력한다.

제한

노트