#P18311. Are the nodes reachable?
Are the nodes reachable?
Are the nodes reachable?
给定一个有 个节点、 条有向边的有向无环图,节点编号为 到 。
你需要回答 次可达性询问。每次给定两个节点 :
- 如果沿原图的有向边可以从 到达 ,输出 ,表示不需要增加道路。
- 否则,你可以在任意两个节点之间修建一条临时有向边,使 可以从 到达。新增从 到 的边的费用为 。
求所需的最小费用。每次询问结束后,新增加的边会被删除,后续询问仍基于原图。
可以在出发前沿原边行进,也可以在经过新增边后继续沿原边行进。只能新加一条边;新增边不要求继续保持图无环。节点到自身可通过长度为0的路径到达。
输入格式
第一行一个整数 ,表示测试用例数。
对每个测试用例:
- 第一行两个整数 。
- 接下来 行,每行两个整数 ,表示原图中存在从 到 的有向边。
- 接下来一行一个整数 。
- 接下来 行,每行两个整数 ,表示一次询问。
原图保证无有向环。原题没有额外禁止同向平行边。
输出格式
每次询问输出一行一个整数,表示最小费用。
数据范围
- 。
- ,。
- 每条原边满足 ,。
- ;每次询问的节点满足 ,允许 。
- 所有测试用例的 之和不超过 , 之和不超过 , 之和不超过 。
费用依据原节点编号计算,编号不一定是拓扑序。
样例
输入
1
4 4
1 2
1 3
1 4
4 3
2
2 3
2 4
输出
1
1