化学反应

题目描述:

现有n种化学物质, 为了方便起见, 我们用1, 2, 3 … n来为它们编号. 我们发现, 一些质可以通过化学反应, 变成另一些物质, 比如说1号物质可以通过某一个化学反应, 变成3号物质; 又比如说, 3号物质可以通过某一个化学反应, 变成2号物质. 那么在这个时候, 我们就认为1号物质可以通过某一些反应, 得到2号物质. 注意, 1号物质可以通过反应得到2号物质, 并不代表2号物质可以通过反应变成1号物质, 即, 化学反应是单向的. 现在, 我们已知一些化学反应, 同时给出一些询问, 询问一种物质通过给定的反应是否可以得到另一种物质.

输入格式:

第1行两个整数n, m, 表示已知n种化学物质, m个化学反应;

第2行到第m + 1行, 每行两个整数u, v, 表示编号为u的物质通过某个化学反应可以变成v物质;

第m + 2行一个整数q, 表示有q组询问;

接下来的q行每行两个整数u, v, 你要判断这两种物质是否可以相互转化(即u可以变成v且v可以变成u). 假如可以, 则输出1, 否则输出0.

输出格式:

总共q行, 每行一个数字1或0.

样例输入:

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

样例输出:

0
1

提示:

样例解释:

1号物质可以变成3号物质再变成2号物质, 但2号物质不能变成1号物质, 因此第一个询问输出0;

2号物质可以变成4号物质再变成3号物质; 3号物质可以直接变成2号物质, 因此第二个询问输出1.

 

数据范围:

3 ≤ n ≤ 100000

2 ≤ m ≤ 100000

1 ≤ q ≤ 1000000

 

注意:

可能存在一种反应使得一种物质变为其自身, 即u = v;

可能存在u = v的询问. 我们认为一种物质无需发生变化就是自身, 因此对于这种情况请输出1

时间限制: 1000ms
空间限制: 256MB

---