Strictly Decreasing Walk in a Directed Graph

You are given a directed graph with \(n\) nodes and \(m\) edges. Each edge is assigned a unique intimacy value from \(1\) to \(m\) – the larger the value, the higher the intimacy. The nodes are numbered \(1,2,\dots,n\) with node \(1\) representing the kindergarten gate. Note that only edges have intimacy values.

You are also given \(k\) queries. In the \(i\)th query, you are provided with a starting node \(x_i\) and an allowable intimacy range \([l_i,r_i]\). Your task is to determine whether there exists a path from \(x_i\) to node \(1\) that strictly adheres to the following conditions:

• You may only use edges whose intimacy values lie in the interval \([l_i,r_i]\).
• If the path uses edges with intimacy values \(e_1,e_2,\dots,e_t\) in the order they are taken, then they must satisfy \(e_1 > e_2 > \cdots > e_t\) (strictly decreasing).

For each query, output 1 if such a path exists; otherwise, output 0.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(k\) which represent the number of nodes, edges, and queries, respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\) indicating a directed edge from node \(u\) to node \(v\). These edges are given in order, meaning the first edge has an intimacy value of \(1\), the second \(2\), and so on until \(m\).

The following \(k\) lines each contain three integers \(x_i\), \(l_i\), and \(r_i\) describing a query: the starting node and the allowed intimacy range.

outputFormat

For each query, print a single line containing 1 if there exists a valid path from \(x_i\) to node \(1\) under the given constraints; otherwise, print 0.

sample

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

1
1
0