ANTTT  The Ant
There are n sticks lying on the ground. The Ant can move only along the sticks. It can go from one stick to another only if the sticks intersect or touch each other. Help the Ant find out if it can reach the stick y from the stick x.
Input
The first line of the input contains number t – the amount of tests. Then t test descriptions follow. The first line of each test contains two integers n and m  the number of stick and the number of queries. Next n lines contain four integers Ax, Ay, Bx, By  the coordinates of the endpoints of a stick. You may consider stick to be straight segment on a plane. The next m lines contain two integers each x and y which are the queries.
Constraints
1 <= t <= 100
1 <= n, m <= 1000
10000 <= Ax, Ay, Bx, By <= 10000
1 <= x, y <= n
Output
For each query print "YES" if the Ant can reach the stick number y from the stick number x, otherwise print "NO".
Example
Input:2
3 3
1 3 4 3
3 4 3 1
3 1 5 1
1 2
1 3
2 2
3 3
1 1 3 1
2 1 3 1
3 2 4 1
1 2
1 3
2 3
Output:YES
YES
YES
YES
NO
NO
hide comments
nadstratosfer:
20200121 11:18:30
Excellent problem. Pythonists must use PyPy here. 

asfd221:
20190824 20:16:38
Do not let precision error, get in way of AC. 

jkks1234:
20190111 11:51:46
Union find Ac in 1 go. 

surajkumar_cse:
20181216 22:43:19
Is there any better way to form intersect function? Except that of orientation. 

poorani_ravi:
20180601 11:30:56
How is it an "YES" for 1 3 4 3 and 3 1 5 1? They are parallel, aren't they? 

atikahamedutso:
20180121 12:01:23
got ac in one go :D 

rnc_123:
20160502 16:56:44
yep did it by union find ..gets accepted..good one..!!


Deepak :
20160125 11:19:24
don't know ..what was wrong with my first submission..just changed int to long long int ..union find.nice one.. 

Rishav Goyal:
20140527 18:57:09
@Sppoky : i think i have covered each & every case , WA, could u plese give me some tricky case ?


Spooky:
20090728 08:11:24
yep... 
Added by:  Spooky 
Date:  20090602 
Time limit:  1.111s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Advancement Spring 2009, http://sevolymp.uuuq.com/ author: elmariachi1414 