強連結成分分解

有向グラフG(V, E) を強連結成分に分解せよ。

有向グラフGの強連結成分においては、すべての頂点対u, vについてuとvは互いに到達可能である。

入力

有向グラフG(V, E)と頂点対u, vの質問が以下の形式で与えられる。

|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1
Q
u0 v0
u1 v1
:
uQ-1 vQ-1

|V|, |E| はそれぞれグラフGの頂点の数と辺の数を示す。グラフGの頂点はそれぞれ0, 1, ..., |V|-1 の番号が付けられている。

s_i, t_i はグラフGのi番目の辺であり、頂点s_iから頂点t_iに向かって辺があることを表す。

u_i, v_i はi番目の質問で与えられる頂点対を表す。

出力

各質問について、頂点対が同じ強連結成分に属している場合"1"、そうでない場合"0"と出力する。

制約

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

入力例 1

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

出力例 1

1
0
1
1

---