There are n ants heading for hot pizza! They should be lined up in order to work for pizza! But, some of the ants are not so happy because they think they should get more advantage than some other ants. You need to find a straight line such that, when all ants "projected" onto this line, all advantage pair of ants are satisfied. Can you do that?
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
Each test case starts with a line containing two integers n, m (1<= n<= 100000; 0<= m<= 200000). Each of the next n lines contains two integers xi, yi (-1000000<= xi, yi<= 1000000) indicating the coordinates of each ant. Then m lines follows. Each of the m lines contains two integers ai, bi meaning that the ant ai needs to be in front of bi (1<= ai, bi<= n). You may assume no two ants will be at the same position.
For each test case, output Yes if you can finish this lining up job. Output No otherwise.
1 3 2 0 0 1 1 2 2 1 2 2 3
Yes
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|