Public Judge

pjudge

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21794. 【NOIP Round #6】遍历

统计

题目描述

给定一个 $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$