human
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
def m
What is a the Python program you requested?
assistant
#Here is the Python program you requested.
ain():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a].append(b) for a, b in ab]

    def scc(g_temp):
        g, n = [set(i) for i in g_temp], len(g_temp)
        rg, cmp_, vs = [[] for _ in [0]*n], [0]*n, []
        for v1, v_list in enumerate(g):
            for v2 in v_list:
                rg[v2].append(v1)
        used = [False]*n
        for v in range(n):
            if not used[v]:
                q = [v]
                while q:
                    v = q[-1]
                    used[v] = True
                    while g[v]:
                        i = g[v].pop()
                        if not used[i]:
                            q.append(i)
                            break
                    else:
                        q.pop()
                        vs.append(v)
        used = [False]*n
        kk = [-1]
        for i in range(len(vs)-1, -1, -1):
            if not used[vs[i]]:
                q = [vs[i]]
                kk[0] += 1
                while q:
                    v, k = q[-1], kk[0]
                    used[v], cmp_[v] = True, k
                    while rg[v]:
                        i = rg[v].pop()
                        if not used[i]:
                            q.append(i)
                            break
                    else:
                        q.pop()
        k = kk[0]
        g2 = [set() for _ in [0]*(k+1)]
        for v1, v_list in enumerate(g_temp):
            for v2 in v_list:
                g2[cmp_[v1]].add(cmp_[v2])
        for v, v_set in enumerate(g2):
            if v in v_set:
                g2[v].remove(v)
        g2 = [list(v) for v in g2]
        return g2, cmp_

    s = scc(g)[1]
    q = int(input())
    for i in range(q):
        c, d = map(int, input().split())
        if s[c] == s[d]:
            print(1)
        else:
            print(0)

main()