Logo Daimayuan Online Judge

Home

时间限制:2 s 空间限制:1024 MB

#805. 【模板】最小瓶颈生成树(数据加强版)

附加文件 统计

题目描述

给定一张 $n$ 个点 $m$ 条边的无向图,每条边有一个权值,定义瓶颈路权值为某一条从点 $i$ 到 $j$ 的路径上的最大权值,有 $q$ 个询问,每次询问给出两个点 $(s,t)$,求从 $s$ 到 $t$ 的最小瓶颈路权值。

保证图联通。

输入格式

第一行包含两个正整数 $n(1\leq n\le 10^5)$ 和 $m (1\leq m\leq \min(10^6, \frac{n \times (n-1)}{2})$,表示点数和边数。

第二行到第 $m+1$ 行包含三个整数 $x,y,d(0\leq d\leq 10^9)$,表示 $x$ 和 $y$ 之间连有一条权值为 $d$ 的无向边。

第 $m+2$ 包含一个正整数 $q(1\leq q\leq 10^6)$,表示询问的次数,后面 $q$ 行每行两个正整数 $s,t(1\leq s, t\leq n)$,分别表示起点和终点。

输出格式

对于每次询问,每行输出一个整数,表示最小的瓶颈路权值

注意:由于本道题输入输出规模过大,请注意 IO 优化

样例输入

2 1 
1 2 10
1
1 2

样例输出

10