题目描述

给定一个 $n$ 个点 $m$ 条边的简单无向连通图。

有 $q$ 次询问，每次给定两个不同的点 $x,y$ ，你可以从 $x$ 出发在图上任意游走，直到走到 $y$ 时结束，且除了开始和结束以外不允许走到 $x,y$ 。求出有多少个点 $z$ 使得存在一个游走方案能经过 $z$ ，包括 $x,y$ 。注意你走的路径可以不是简单路径，唯一的限制是不能重复经过 $x$ 和 $y$ 。

输入格式

第一行一个正整数 $T$ ，表示数据组数。每组数据的格式如下：

• 第一行两个正整数 $n,m$ ，表示点数和边数。
• 接下来 $m$ 行，每行两个正整数 $x,y$ ，表示一条 $x$ 到 $y$ 的边。
• 下一行一个正整数 $q$ ，表示询问次数。
• 接下来 $q$ 行，每行两个正整数 $x,y$ ，表示一次询问。

输出格式

对每个询问输出一行一个正整数，表示可以经过的点数。

样例 $1$

input

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

output

2
4
3
3
5

样例 $2\sim 5$

见下发文件中的 ex_*.in/ex_*.out，它们分别对应第 $2\sim 5$ 个子任务。

数据范围

本题采用捆绑测试，你需要通过一个子任务的所有测试点才能得到子任务的分数。

对于所有数据，$1\le T\le 1000, 1\le \sum n\le 2\times 10^5, 1\le \sum m \le 5\times 10^5, 1\le \sum q\le 5\times 10^5$ 。