题目描述

仙界是一张由灵泉和天路组成的图。图上有 $n$ 处灵泉，灵泉蕴含丰富能量，当小 F 位于某处灵泉时，灵泉便会赋予他一次能量。有 $m$ 条天路，第 $i$ 条连接 $a_i$ 和 $b_i$ 处的灵泉，为防止小 F 反复刷能量，所以只能由 $a_i$ 处灵泉走到 $b_i$ 处灵泉。同时，这张图也保证小 F 不存在某种走法使得被某一灵泉赋予超过 $1$ 次能量，即不存在环。

小 F 功力过弱，只有当所有灵泉都为他赋予过能量，他才能获得提升。一日，小 F 获得了 $q$ 本卷轴，第 $i$ 本卷轴会创建一条从 $p_i$ 处灵泉走到 $q_i$ 处灵泉的天路。但是物以稀为贵，他只能用其中一本。并且小 F 很诚信，即使在加上这条天路后，存在某种走法使得能被某一灵泉赋予超过 $1$ 次能量，他也觉得这是毫无意义的，所以不会这样走。

现在对于 $1\le i\le q$ ，小 F 请你告诉他如果使用第 $i$ 本卷轴，图上是否存在一种走法使得他能获得提升，即所有灵泉都为他赋予过能量。

输入格式

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行两个整数 $a_i,b_i$ 。

第 $m+2$ 行，一个整数 $q$ 。

接下来 $q$ 行，每行两个整数 $p_i,q_i$ 。具体含义如上所述。

输出格式

共一行长度为 $q$ 的 01 串 $s$ ， $s_i=1$ 表示使用第 $i$ 个卷轴能获得提升，反之不能。

输入输出样例 #1

输入 #1

5 5
3 1
1 2
2 5
1 4
4 5
3
5 1
4 2
1 5

输出 #1

010

说明/提示

【样例 1 解释】

对于第一个卷轴，虽然走法 $3\to 1\to 4 \to 5\to 1\to 2$ 能让他获得提升，但是他并不会这样走，因为被第 $1$ 处灵泉赋予了 $2$ 次能量。可以证明没有其他合法走法让他获得提升。

对于第二个卷轴，走法 $3\to 1\to 4\to 2\to 5$ 是合法的。

【样例 2】

见选手目录下的 $walk/walk2.in$ 与 $walk/walk2.ans$ 。

【样例 3】

见选手目录下的 $walk/walk3.in$ 与 $walk/walk3.ans$ 。

【样例 4】

见选手目录下的 $walk/walk4.in$ 与 $walk/walk4.ans$ 。

【数据范围】

本题输入量较大，建议使用快读，见选手目录下的 $read.cpp$ 。

对于所有测试点，

• $1\leq n\le 5\times 10^5$ ， $1\le m\leq \min\left(\frac{n(n-1)}{2},10^6\right)$ ， $1\le q\le 10^6$ ，
• 不存在 $1\le i<j\le m$ 满足 $a_i=a_j$ 且 $b_i=b_j$ ，不存在 $1\le i\le m$ 满足 $a_i=b_i$ ，
• $1\le a_i,b_i,p_i,q_i\le n$ 。

• 特殊性质 A： $m=n-1$ 。
• 特殊性质 B： $m=n$ 。
• 特殊性质 C：所有 $p_i$ 相同。