human
Write me a the Python program you requested given the following:
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.

Constraints

* 1 ≤ |V| ≤ 10,000
* 0 ≤ |E| ≤ 30,000
* 1 ≤ Q ≤ 100,000

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.

Example

Input

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

Output

1
0
1
1
assistant
#Here is the Python program you requested.

from collections import UserList
class Stack(UserList):
    def __init__(self):
        UserList.__init__(self)
        self.contains = set()
    def __contains__(self, x):
        return x in self.contains
    def __and__(self, x):
        return self.contains & x
    def push(self, x):
        if x in self.contains:
            return
        self.data.append(x)
        self.contains |= {x}
    def pop(self):
        x = self.data.pop()
        self.contains -= {x}
        return x

def search(g, g_dash,v):
    # search postorder
    visited = set()
    postorder = []
    for root in range(v):
        if root in visited:
            continue
        route = Stack()
        route.push(None)
        dfs_stack = [(root, None)]            
        while dfs_stack:
            u, prev = dfs_stack.pop()
            if u in visited:
                continue
            visited |= {u}
            dfs_stack.extend((v, u) for v in g[u] - visited)
            while route[-1] != prev:
                postorder.append(route.pop())
            route.push(u)
        while route[-1] is not None:
            postorder.append(route.pop())

    # reverse search lowest
    visited.clear()
    lowest = [None] * v
    for root in postorder[::-1]:
        if root in visited:
            continue
        dfs_stack = [root]
        while dfs_stack:
            u = dfs_stack.pop()
            if u in visited:
                continue
            visited |= {u}
            lowest[u] = root
            dfs_stack.extend(g_dash[u] - visited)
    return lowest

from sys import stdin
from collections import defaultdict
readline = stdin.readline

def main():
    v, e = map(int, readline().split())
    g = defaultdict(set)
    g_dash = defaultdict(set)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s] |= {t}        
        g_dash[t] |= {s}        
    
    lowest = search(g,g_dash, v)
    q = int(readline())
    for u, v in [map(int, readline().split()) for _ in range(q)]:
        print(1 if lowest[u] ==...