Road Direction Planning

A grid-shaped city has N horizontal roads and M vertical roads. At each of the N x M intersections of these roads, there is one village. All roads were originally usable in both directions, but to reduce accidents, every road must now be made one-way. Each horizontal road must be directed either left to right or right to left, and each vertical road must be directed either top to bottom or bottom to top.

The city has K direct bus routes. Each bus must travel from one village to another. After the road directions are chosen, every bus must still be able to travel from its start village to its destination by a shortest path. In addition, each bus route must be simple and may use at most two roads: at most one horizontal road and at most one vertical road.

Therefore, if the start and destination differ in both row and column, there are only two possible route shapes. The bus may first follow the horizontal road through its start village and then the vertical road through its destination, or it may first follow the vertical road through its start village and then the horizontal road through its destination. At least one of these two routes must agree with the chosen road directions.

Given the road sizes and bus routes, determine whether it is possible to choose directions for all roads so that every bus satisfies these conditions.

The first line contains the number of test cases T (1 <= T <= 10).

For each test case, the first line contains three integers N, M, and K. N is the number of horizontal roads, M is the number of vertical roads, and K is the number of bus routes.

Each of the next K lines contains four integers A, B, C, and D describing one bus route. The bus starts at the village where horizontal road A and vertical road B meet, and must go to the village where horizontal road C and vertical road D meet.

Horizontal roads are numbered from 1 to N, and vertical roads are numbered from 1 to M. A bus may have the same start and destination.

For each test case, print one line. Print Yes if the road directions can be chosen to satisfy all conditions, and No otherwise.