BOJ 1739 도로 정비하기

문제 링크:

문제 내용

$N$개의 가로 도로와 $M$개의 세로 도로가 $NM$개 지점에서 서로 교차하는 형태의 도로망이 있습니다. $i$번 가로 도로와 $j$번 세로 도로가 교차하는 지점을 $(i, j)$라고 합시다.

$K$대의 차가 각각 출발지 $(a_i, b_i)$에서 도착지 $(c_i, d_i)$로 이동하려고 하는데, 각 차는 최대 하나의 가로 도로와 최대 하나의 세로 도로만을 이용할 수 있습니다.

$K$대의 차가 조건을 충족하면서 출발지에서 도착지로 이동할 수 있도록 각각의 도로를 일방통행으로 만들 수 있는지 판별하세요.

입력

첫 줄에 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 10$)

각 테스트 케이스에 대해, 첫 줄에 $N$, $M$, $K$가 주어집니다. ($1 \le N, M, K \le 1000$)

다음 $K$줄에는 각각의 차의 출발지와 도착지를 나타내는 값 $a_i$, $b_i$, $c_i$, $d_i$가 순서대로 주어집니다. ($1 \le a_i, c_i \le N$, $1 \le b_i, d_i \le M$)

출발지와 도착지는 같을 수 있습니다.

출력

각 테스트 케이스에 대해, 각각의 도로를 일방통행으로 만들 방법이 있으면 Yes, 아니면 No를 출력합니다.

문제 풀이