시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 83 21 17 24.286%

문제

가로로 N(1≤N≤1,000)개, 세로로 M(1≤M≤1,000)개의 도로가 나 있는 도시가 있다. 또한 이 도로들의 N×M개의 교점들에는 마을이 있다. 이 도로들을 통해서 차들은 자유롭게 마을 사이를 오갈 수 있었는데, 도로들이 좁아서 교통사고가 자주 발생하게 되었다. 이를 막기 위해서, 이 도시의 시장은 각각의 도로들에 방향성을 주어서, 그 도로를 이용할 때는 한 쪽 방향으로만 차가 다닐 수 있도록 하려 한다.

이 도시에는 K(1≤K≤1,000)개의 버스가 있는데, 버스는 한 마을에서 다른 한 마을로 이동하는 직행 버스들이다. 시장은 대중교통을 중요시하는 사람이기 때문에, 버스들을 최우선적으로 고려하여 도로에 방향성을 주려 한다. 즉, 도로를 정비한 후에 각 버스들이 최단거리로 다닐 수 있도록 방향성을 주려 한다. 또한 도로의 혼잡을 줄이기 위해서, 각각의 버스들이 최대 두 개(가로 도로 한 개, 세로 도로 한 개)의 도로만을 이용하는 단순 경로를 지나서 다닐 수 있도록 하려 한다. 이해를 돕기 위해 아래 그림을 보자.

아래 그림에서 왼쪽 위의 점은 시작점을, 오른쪽 아래의 점은 도착점을 나타낸다. a) 의 경우는 방향이 어긋나기 때문에 잘못된 경로이다. b) 의 경우는 방향은 어긋나진 않지만 단순 경로가 아닌 경우이며, c) 가 올바른 경우이다.

이러한 계획을 세우기는 했지만, 시장은 실제로 이러한 조건을 만족하면서 도로들에 방향성을 줄 수 있는지 궁금해졌다. 도로에 대한 정보와 각 버스에 대한 정보가 주어졌을 때, 이러한 조건을 만족하면서 도로들에 방향성을 줄 수 있는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 데이터의 개수 T(1≤T≤10)가 주어진다. 각 테스트 데이터의 첫째 줄에는 세 정수 N, M, K가 주어진다. 다음 K개의 줄에는 각 버스의 운행 정보를 나타내는 네 정수 A, B, C, D가 주어진다. 이는 버스가 A번 가로 도로와 B번 세로 도로가 교차하는 마을에서, C번 가로 도로와 D번 세로 도로가 교차하는 마을로 이동함을 의미한다. 가로 도로의 범위는 1부터 N까지이며, 세로 도로의 범위는 1부터 M까지이다.

출력

T개의 줄에, 각 테스트 데이터에 대한 답을 출력한다. 가능한 경우에는 Yes를, 불가능한 경우에는 No를 출력한다.

예제 입력

2
6 6 2
1 1 6 6
6 6 1 1
7 7 3
1 1 1 6
6 1 6 6
6 6 1 1

예제 출력

Yes
No

힌트

출처

  • 문제를 번역한 사람: author5