Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
ACM Underground
 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 317 Accepted: 102

Description

For example, in the following figure, there are five metro lines, with three policemen located at black circles. You may travel from s to d without meeting any police along the path l1 -- l4, but it is not possible to travel from s to d' without confronting any policemen.

In this problem, you must write a program that reads the metro line specifications, the police locations, and your source and destination, and determine whether it is possible to travel from the given source to the given destination without meeting any policeman.

Input

The first number in the input line, T is the number of test cases. The first line of each test case contains two integers n and m (1 ≤ m ≤ 100, 1 ≤ n ≤ 3000) which are the number of lines and the number of policemen. The second line contains four integers xs ys xd yd which are the coordinates of the source and the destination points respectively. You may assume these two points lie on metro lines. Following the second line, there are n lines of the form x1 y1 x2 y2 describing the metro lines where (x1, y1) and (x2, y2) specify the endpoints of the metro line. After this, there are m lines each containing a pair of integers x y that specify the location of a policeman. All coordinates are arbitrary integer numbers.

Output

The output contains T lines, each corresponding to an input test case in that order. The output line contains a single word YES or NO depending on whether there is a safe way to travel from source to destination or not.

Sample Input

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

Sample Output

```YES
NO
```

Source

[Submit]   [Go Back]   [Status]   [Discuss]