← 返回题目列表

Codeforces · 42/E

E. 巴尔德曼和军队

中文机器翻译题面 查看原题

巴尔德曼是一位扭曲大师。他拥有一种独特的能力——创造虫洞!给定空间中的两个位置,鲍德曼可以制造一个虫洞,从而可以在它们之间双向移动。不幸的是,这样的手术对巴尔德曼来说并不是免费的:每一个虫洞都会让他失去大量的头发。

由于如此非凡的能力,巴尔德曼引起了军方的注意。他被赋予一项特殊任务。但首先要说的是。

军事基地由多个地下物体组成,其中一些通过双向隧道相连。每对对象之间必然存在一条穿过隧道系统的路径。此外,恰好有两个对象与曲面相连。出于安全目的,巡逻人员每天都会检查隧道系统:他进入与地面相连的物体之一,在基地内行走至少经过每条隧道一次,然后从与地面相连的物体之一离开。他可以通过同一个物体进入和离开,也可以通过不同的物体进入和离开。军方管理层注意到巡逻队多次巡视一些隧道,并决定优化流程。现在他们面临着一个问题:需要建立一个虫洞系统,以允许巡逻队精确地通过每个隧道一次。同时,允许巡逻队多次通过每个虫洞。

这就是鲍德曼发挥作用的地方:他是规划和建造虫洞系统的人。对他来说不幸的是,由于严格保密,军方无法告诉他隧道的布置情况。相反,他们坚持认为他的门户系统解决了满足给定条件的任何隧道布置的问题。尽管如此,巴尔德曼还是有一些信息:他知道他可以连接哪些对象对以及这将花费他多少(头发)。此外,明天他将被告知哪些物体(恰好是两个)与表面相连。当然,我们的英雄决定不浪费任何时间并计算完成某些对象对(他发现可能是与表面连接的对象)的工作的最小成本。帮助巴尔德曼!

输入

输入的第一行包含一个自然数 n (2 ≤ n ≤ 100000) — 军事基地上的物体数量。第二行 — 一个数字 m (1 ≤ m ≤ 200000) — 鲍德曼可以制造的虫洞数量。接下来的m行描述了虫洞:每行包含三个整数a,b,c(1≤a,b≤n,1≤c≤100000)——可以连接的物体的数量以及秃头制造这个虫洞需要花费的头发数量。

下一行包含一个自然数 q (1 ≤ q ≤ 100000) — 查询数。最后,最后 q 行分别包含一个查询的描述 — 一对不同对象的数字 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。一对物体之间可能存在多个虫洞。

输出

你的程序应该输出q行,每个查询一行。第 i 行应该包含一个整数 - 第 i 个查询的答案:如果 ai 和 bi 是与表面连接的两个对象,则虫洞系统允许对任何隧道系统进行最佳巡逻(满足给定条件)的最小成本(以头发为单位),如果无法制作这样的虫洞系统,则为“-1”。

示例

输入 #1

2
1
1 2 3
1
1 2

输出 #1

0

输入 #2

3
1
1 2 3
2
1 2
1 3

输出 #2

-1
3