8606: GRL_3_C : Strongly Connected Components
[Creator : ]
Description
A direced graph is strongly connected if every two nodes are reachable from each other. In a strongly connected component of a directed graph, every two nodes of the component are mutually reachable.
Input
A directed graph G(V,E) and a sequence of queries where each query contains a pair of nodes u and v.
|V| |E|
$s_0\ t_0$
$:$
$s_{|E|−1}\ t_{|E|−1}$
$Q$
$u_0\ v_0$
$:$
$u_{Q−1}\ v_{Q−1}$
|V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.
$s_i$ and $t_i$ represent source and target nodes of i-th edge (directed).
$u_i$ and $v_i$ represent a pair of nodes given as the i-th query.
Output
For each query, pinrt "1" if the given nodes belong to the same strongly connected component, "0" otherwise.
Constraints
1 ≤ |V| ≤ 10,000
0 ≤ |E| ≤ 30,000
1 ≤ Q ≤ 100,000
0 ≤ |E| ≤ 30,000
1 ≤ Q ≤ 100,000
Sample 1 Input
5 6
0 1
1 0
1 2
2 4
4 3
3 2
4
0 1
0 3
2 3
3 4
Sample 1 Output
1
0
1
1