#P18311. Are the nodes reachable?

Are the nodes reachable?

Are the nodes reachable?

给定一个有 NN 个节点、MM 条有向边的有向无环图,节点编号为 11 到 NN。

你需要回答 QQ 次可达性询问。每次给定两个节点 U,VU,V:

  • 如果沿原图的有向边可以从 UU 到达 VV,输出 00,表示不需要增加道路。
  • 否则,你可以在任意两个节点之间修建一条临时有向边,使 VV 可以从 UU 到达。新增从 XX 到 YY 的边的费用为 ∣X−Y∣|X-Y|。

求所需的最小费用。每次询问结束后,新增加的边会被删除,后续询问仍基于原图。

可以在出发前沿原边行进,也可以在经过新增边后继续沿原边行进。只能新加一条边;新增边不要求继续保持图无环。节点到自身可通过长度为0的路径到达。

输入格式

第一行一个整数 TT,表示测试用例数。

对每个测试用例:

  • 第一行两个整数 N,MN,M。
  • 接下来 MM 行,每行两个整数 U,VU,V,表示原图中存在从 UU 到 VV 的有向边。
  • 接下来一行一个整数 QQ。
  • 接下来 QQ 行,每行两个整数 U,VU,V,表示一次询问。

原图保证无有向环。原题没有额外禁止同向平行边。

输出格式

每次询问输出一行一个整数,表示最小费用。

数据范围

  • 1≤T≤1001\le T\le100。
  • 1≤N≤1041\le N\le10^4,1≤M≤8⋅1041\le M\le8\cdot10^4。
  • 每条原边满足 1≤U,V≤N1\le U,V\le N,U≠VU\ne V。
  • 1≤Q≤1061\le Q\le10^6;每次询问的节点满足 1≤U,V≤N1\le U,V\le N,允许 U=VU=V。
  • 所有测试用例的 NN 之和不超过 10510^5,MM 之和不超过 10510^5,QQ 之和不超过 10610^6。

费用依据原节点编号计算,编号不一定是拓扑序。

样例

输入

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

输出

1
1