题目描述
给定一个 $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$ 。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $1\le T\le 5,n,m,q\le 20$ | $10$ |
| $2$ | $\sum n\le 1000,\sum m,\sum q\le 2000$ | $20$ |
| $3$ | $m=n-1$ | $20$ |
| $4$ | 保证图删除任意一个点后仍然连通 | $10$ |
| $5$ | 无特殊性质 | $40$ |