Problem:


Strongly Connected Components

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|
s0 t0
s1 t1
:
s|E|-1 t|E|-1
Q
u0 v0
u1 v1
:
uQ-1 vQ-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.

si and ti represent source and target nodes of i-th edge (directed).

ui and vi 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

Sample Input 1

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

Sample Output 1

1
0
1
1



Sample 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 output:
1
0
1
1

Submission status: WA: Presentation Error

Solution code:
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)
    c = get_strongly_connected_components(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result), end="")


def get_strongly_connected_components(edges, r_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = 1

    def get_order(v):
        order[v] = 1
        nonlocal k
        for dest in edges[v]:
            if order[dest] == 0:
                get_order(dest)
        order[v] = k
        k += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in r_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    get_order(0)
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()