道路相遇

题目描述

在 H 国的小 w 决定到从城市 $u$ 到城市 $v$ 旅行,但是此时小 c 由于各种原因不在城市 $u$,但是小 c 决定到在中途与小 w 相遇 由于 H 国道路的原因,小 w 从城市 $u$ 到城市 $v$ 的路线不是固定的,为了合理分配时间,小 c 想知道从城市 $u$ 到城市 $v$ 有多少个城市小 w 一定会经过,特别地,$u, v$ 也必须被算进去,也就是说无论如何答案不会小于 2 由于各种特殊的原因,小 c 并不知道小 w 的起点和终点,但是小 c 知道小 w 的起点和终点只有 $q$ 种可能,所以对于这 $q$ 种可能,小 c 都想知道小 w 一定会经过的城市数 H 国所有的边都是无向边,两个城市之间最多只有一条道路直接相连,没有一条道路连接相同的一个城市 任何时候,H 国不存在城市 $u$ 和城市 $v$ 满足从 $u$ 无法到达 $v$

输入输出格式

输入格式


第一行两个正整数 $n,m$,表示 H 国的城市数,以及道路数。 下面 $m$ 行,每行两个不同的正整数 $u, v$,表示城市 $u$ 到城市 $v$ 之间有一条边。 然后一行一个正整数 $q$。 接下来 $q$ 行,每行两个正整数 $u, v$ 表示小 w 旅行的一种可能的路线

输出格式


输出共 $q$ 行,每行一个正整数

输入输出样例

输入样例 #1

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

输出样例 #1

3

说明

从城市 $1$ 到城市 $5$ 总共有 $4$ 种可能 : $1 \to 2 \to 3 \to 4 \to 5$ $1 \to 2 \to 3 \to 5$ $1 \to 2 \to 4 \to 5$ $1 \to 3 \to 5$ 可以发现小 w 总会经过城市 $1,3,5$,所以答案为 $3$ 你可以认为小 w 不会经过相同的城市两次,当然,如果你认为可以经过相同的城市两次也不会影响答案 subtask1 : 15分,$m = 5, q = 50$ subtask2 : 15分,$n = 100, q = 5000$ subtask3 : 20分,$n = 3000, q = 5\times 10^5$ subtask4 : 20分,$n = 499999, q = 5 \times 10^5, m = n-1$ subtask5 : 30分,$n = q = 5 \times 10^5$ 对于所有数据 : $1\leq n\leq 5 \times 10^5, 1\leq q\leq 5\times 10^5, 1\leq m\leq \min(\frac{n(n-1)}{2}, 10^6)$