OI题库

【问题描述】

有向图G=(V,E)的平方是图G^2=(V,E^2)，该图满足下列条件：(u,w)∈E^2当且仅当对v∈V，有(u, v)∈E，且(v,w)∈E。亦即，如果图G中顶点u和w之间存在着一条恰包含两条边的路径时，则G^2必包含该边(u,w)。
请编程序对于给定的有向图G，查询边(u,w)是否存在于平方图G^2中。

【输入文件】

第一行有两个整数，v(1<=v<=100000)，m(1<=m<=1000)，其中v表示图G的顶点个数，（顶点按1~v编号）；
接下来有m行，每行包含4个整数u1,u2,v1,v2，表示在图G中，顶点区间[u1,u2]中的每一个顶点至顶点区间[v1,v2]中的每一个顶点都有边相连；
接下来有一行，一个整数n（1<=n<=1000），表示查询的个数；
接下来有n行，每一行有4个整数，x1,x2,y1,y2，表示一个询问，即询问在平方图G^2中，其顶点区间[x1,x2]中的每一个顶点至顶点区间[y1,y2]中的每一个顶点是否都有边。

【输出文件】

对于每一个查询，如果结果为“是”则输出"Yes"，否则输出"No"，如果有多个查询，每个结果单独占一行。

【样例输入】
ljb.in

6 2
1 3 5 6
4 5 2 3
1
2 3 4 6

【样例输出】

ljb.out

No

注：图G与G^2中的边数均不会超过2000000.