#P13300. 遍历

    ID: 12484 传统题 文件IO:travel 3000ms 512MiB 尝试: 109 已通过: 16 难度: 7 上传者: 标签>CF2300提高+/省选-点双连通分量low-link圆方树DFS 序树上倍增补集转化

遍历

题目描述

给定一个 nn 个点 mm 条边的简单无向连通图。

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

输入格式

第一行一个正整数 TT ,表示数据组数。每组数据的格式如下:

  • 第一行两个正整数 n,mn,m ,表示点数和边数。
  • 接下来 mm 行,每行两个正整数 x,yx,y ,表示一条 xx 到 yy 的边。
  • 下一行一个正整数 qq ,表示询问次数。
  • 接下来 qq 行,每行两个正整数 x,yx,y ,表示一次询问。

输出格式

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

样例 11

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

样例 2∼52\sim 5

见下发文件中的 ex_*.in/ex_*.out,它们分别对应第 2∼52\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$

大数据