道路相遇

在 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 总共有 4 种可能 :

1 \to 2 \to 3 \to 4 \to 5

1 \to 2 \to 3 \to 5

1 \to 3 \to 4 \to 5

1 \to 3 \to 5

可以发现小 w 总会经过城市 1,3,5，所以答案为 3

对于所有数据 : 1\leq n\leq 10^5, 1\leq q\leq 10^5, 1\leq m\leq \min(\frac{n(n-1)}{2}, 10^6)

luogu