유령의 집 조명

유령이 사는 집을 물려받았다. 집의 평면도는 $n \times n$ 정사각 격자이고 내부 벽은 없다. 정해진 칸에 램프가 $l$개 놓여 있다.

램프는 자기가 있는 행을 밝히거나 자기가 있는 열을 밝힌다. 둘을 동시에 밝히지는 못한다. 빛은 고른 직선을 따라 양쪽으로 $r$칸까지 뻗으므로, 바깥 벽에 막히지 않은 램프는 자기 칸을 포함해 최대 $2r + 1$칸을 밝힌다.

어떤 칸이 행을 밝히는 램프 두 개에 함께 밝혀지거나 열을 밝히는 램프 두 개에 함께 밝혀지면, 그 칸이 너무 환해져서 유령이 영원히 떠나고 집값이 떨어진다. 행을 밝히는 램프 하나와 열을 밝히는 램프 하나가 함께 밝히는 칸은 아무 문제가 없다.

모든 램프에 행이나 열을 하나씩 배정해서 유령을 쫓아내지 않을 수 있는지 판정한다.

첫째 줄에 세 양의 정수 $n$, $r$, $l$이 주어진다 ($1 \le n, r, l \le 1000$).

다음 $l$개 줄에 각각 두 양의 정수 $r_i$, $c_i$가 주어진다 ($1 \le r_i, c_i \le n$). $r_i$행 $c_i$열에 램프가 하나 있다는 뜻이다.

램프의 위치는 모두 다르다.

조건을 지키는 배정이 있으면 1, 없으면 0을 한 줄에 출력한다.