Problem E
Manhattan

You are the mayor of a city with severe traffic problems. To deal with the situation, you have decided to make a new plan for the street grid. As it is impossible to make the streets wider, your approach is to make them one-way (only traffic in one direction is allowed on a street), thus creating a more efficient flow of traffic.

The streets in the city form an orthogonal grid – like on Manhattan avenues run in north-south direction, while streets run in east-west direction. Your mission is to make all the streets and avenues one-way, i.e., fix the direction in which traffic is allowed, while maintaining a short driving distance between some ordered pairs of locations. More specifically, a route in the city is defined by two street-avenue crossings, the start and goal location. On a one-way street grid, a route has a legal path if it is possible to drive from the start location to the goal location along the path passing streets and avenues in their prescribed direction only.

A route does not define a specific path between the two locations – there may be many possible paths for each route. A legal path in a one-way street grid is considered simple if it requires at most one turn, i.e., a maximum of one street and one avenue need to be used for the path.

When travelling by car from one location to another, a simple path will be preferred over a non-simple one, since it is faster. However, as each street in the grid is one-way, there may always be routes for which no simple path exists. On your desk lies a list of important routes which you want to have simple paths after the redesign of the street grid.

Your task is to write a program that determines if it is possible to fix the directions of the one-way streets and avenues in such a way that each route in the list has at least one simple path.

Figure 1: a) An illegal path. b) A legal but non-simple path. c) A simple path.

Input

On the first line of the input, there is a single integer $1 \le n \le 10$, telling how many city descriptions that follow. Each city description begins with a line containing three integers: the number of streets $1 \le S \le 30$, and avenues $1 \le A \le 30$ in the street grid, and the number of routes $1 \le m \le 200$ that should have at least one simple path. The next $m$ lines define these routes, one on each line. Each route definition consists of four integers, $s_1$, $a_1$, $s_2$ and $a_2$, where the start location of the route is at the crossing of street $s_1$ and avenue $a_1$, and the goal location is at the crossing of street $s_2$ and avenue $a_2$. Obviously, $1 \le s_1, s_2 \le S$ and $1 \le a_1, a_2 \le A$.

Output

For each city, your program should output “Yes” on a single line if it is possible to make the streets and avenues one-way, so that each route has at least one simple path. Otherwise output “No”.

3
6 6 2
1 1 6 6
6 6 1 1
7 7 4
1 1 1 6
6 1 6 6
6 6 1 1
4 3 5 1
9 8 6
2 2 4 4
4 5 3 2
3 4 2 2
3 2 4 4
4 5 2 2
2 1 3 4

Yes
No
No