Range Reachability Query

You are given a directed acyclic graph with $n$ vertices and $m$ edges. The vertices are labeled by $1,2,\dots,n$, and the edges are labeled by $1,2,\dots,m$.

You will be given $q$ queries. In the $i$-th query, you will be given four integers $u_i$, $v_i$, $l_i$ and $r_i$ ($1\leq l_i\leq r_i\leq m$). You need to answer whether vertex $u_i$ can reach vertex $v_i$ when only edges labeled by $k$ ($l_i\leq k\leq r_i$) are available.

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains three integers $n,m$ and $q$ ($2 \leq n \leq 50\,000$, $1\leq m\leq 100\,000$, $1\leq q\leq 50\,000$), denoting the number of vertices, the number of edges, and the number of queries.

Each of the following $m$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i < v_i\leq n$), denoting a directed edge from vertex $u_i$ to vertex $v_i$.

In the next $q$ lines, the $i$-th line contains four integers $u_i$, $v_i$, $l_i$ and $r_i$ ($1\leq u_i < v_i\leq n$, $1\leq l_i\leq r_i\leq m$), describing the $i$-th query.

For each query, print a single line. If vertex $u_i$ can reach vertex $v_i$ when only edges labeled by $k$ ($l_i\leq k\leq r_i$) are available, print ''$\texttt{YES}$''. Otherwise, print ''$\texttt{NO}$''.

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

NO
YES
YES
YES
NO

2022“杭电杯”中国大学生算法设计超级联赛（3）