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
impor
assistant
#Here is the Python program you requested.
t sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]
    outdeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        E[u].append(v)
        rev[v].append(u)
        outdeg[u] += 1

    order = []
    used = [False] * n
    # for v in range(n):
    #     if used[v]:
    #         continue
    #     used[v] = True
    #     stack = [(~v, -1), (v, -1)]
    #     while stack:
    #         v, p = stack.pop()
    #         if v >= 0:
    #             for nv in E[v]:
    #                 if used[nv]:
    #                     outdeg[v] -= 1
    #                 else:
    #                     used[nv] = True
    #                     stack.append((~nv, v))
    #                     stack.append((nv, v))
    #         else:
    #             v = ~v
    #             if outdeg[v] == 0:
    #                 order.append(v)
    #             if p != -1:
    #                 outdeg[p] -= 1

    def dfs(v):
        if used[v]:
            return
        used[v] = True
        for nv in E[v]:
            dfs(nv)
        order.append(v)
    any(dfs(v) for v in range(n))
    order.reverse()
    color = [-1] * n
    ans = []
    cnt = -1
    for v in order:
        if color[v] != -1:
            continue
        cnt += 1
        color[v] = cnt
        stack = [v]
        while stack:
            v = stack.pop()
            for nv in rev[v]:
                if color[nv] != -1:
                    continue
                color[nv] = cnt
                stack.append(nv)

    for _ in range(int(input())):
        u, v = map(int, input().split())
        print(int(color[u] == color[v]))
resolve()