ACM Underground#5045
ACM is a town with a very special underground metro system, consisting of multiple railway segments, each called a line. Trains run in both directions along every line. Two lines may intersect, and at such an intersection, a passenger can switch from a train on the first line to a train on the second line.
The starting and ending points of your travel are located somewhere on the metro lines. You begin your travel on the metro line that the source point lies on. You may change lines only at intersection points of metro lines, and can continue changing lines at such intersections until you reach your destination.
Your goal is to travel for free, i.e., without ever needing to buy a ticket. The complication is that there are several policemen checking tickets. You do not wish to encounter any of these policemen during your travel.
You may encounter a policeman in exactly two situations: 1. At a line intersection, but only if you actually change lines at the intersection. 2. While moving along a line, if your wagon passes a point where a policeman is located (but not at an intersection).
You know all the policemen's starting locations. Some policemen may be located elsewhere on the map, not on any metro line; you must ignore such policemen. Note that if a policeman is located at a line intersection, he will only check your ticket if you switch lines at that intersection. If a policeman is located somewhere strictly on a line (but not at an intersection), he will check your ticket only if your train passes through that particular point.
For example, in the following figure, the metro consists of five lines and three policemen (marked by black circles). It is possible to travel from to along the path l_1 - l_4 without meeting any policemen. However, it is not possible to travel from to d' without encountering a policeman.
Given the layout of the metro lines, the locations of the policemen, and the coordinates of the start and end points of your travel, determine whether it is possible to travel from the source to the destination without meeting any policeman on your path.
The first line contains the integer , the number of test cases.
Each test case starts with a line containing two integers and (1 \leq m \leq 100, 1 \leq n \leq 3000) — the number of metro lines and the number of policemen, respectively.
The second line contains four integers x_s y_s x_d y_d — the coordinates of the source and the destination points. Both of these points are guaranteed to lie on metro lines.
The next lines describe the metro lines. Each line is given in the format x_1 y_1 x_2 y_2, specifying that the line goes between (x_1, y_1) and (x_2, y_2) (inclusive).
The following lines specify the locations of the policemen. Each is given as two integers , their coordinates. All coordinates are arbitrary integers.
Output lines. For each test case, print YES if it is possible to complete the travel from the source to the destination without encountering any policeman, or NO otherwise.
Example 1