#2547. 蚁巢

蚁巢

Description

NN个蚁巢,编号为1N1~N。第ii个蚁巢的位置是(xi,yi)(xi,yi),没有两个蚁巢在同一位置。所有蚂蚁都遵守一些规律:

①当一只蚂蚁在蚁巣pp时,它总是移动到离pp最近的另一个蚁巣,若有多个蚁巣与pp的距离最小,则它会移动到xx坐标值较小的蚁巣。若仍有平局,则选择yy坐标值较小的蚁巣。当蚂蚁从一个蚁巣移动到另一个蚁巣时,它总是沿着连接它们的线段移动;

②蚂蚁从不停下来,当蚂蚁到达一个蚁巣时,它会立即移动到下一个蚁巣。所以,蚂蚁可以无限次地造访蚁巣;

③所有蚂蚁都以同样的速度移动,所有蚂蚁和蚁巢都可被看作点。

给定两个不同的蚁巣,求两只蚂蚁同时从这两个蚁巣移动,会不会在某个时间相遇?

Format

Input

输入以整数TT10T(T≤10)为开头,表示测试用例的数量。每个测试用例都以整数N和Q2N1051Q105Q(2≤N≤10^5,1≤Q≤10^5)为开头,分别表示蚁巢数和查询数。下面的nn行,每行都包含两个整数XiXiYi109Xi,Yi109Yi(-10^9≤Xi,Yi≤10^9),表示第ii个蚁巢的位置。下面的Q行,每行都包含两个整数i和j1i,jNijj(1≤i,j≤N,i≠j),表示两个给定蚁巢的编号。

Output

对每个测试用例,都输出“CaseCase#X:X:”,其中XX是用例编号,从11开始。然后对每个查询,若两个蚂蚁会相遇,则在一行中输出“YESYES”,否则输出“NONO”。

Samples

2
2 1
0 0
-1 1
1 2
5 2
1 1
3 3
4 4
0 -3
0 -4
1 3
2 4
Case #1:
YES
Case #2:
Yes
No

来源

HDU5809