题目描述

頂点には $1$ から $N$ の番号が、辺には $1$ から $M$ の番号がついた $N$ 頂点 $M$ 辺の連結無向グラフがあります。 辺 $i$ は頂点 $U_i$ と頂点 $V_i$ を結んでおり、重みとして整数 $W_i$ が定められています。 ここで、$1\leq\ s,t\ \leq\ N,\ s\neq\ t$ に対して $d(s,t)$ を以下で定義します。

• 頂点 $s$ と頂点 $t$ を結ぶすべてのパスに対する「パス上の辺の重みの最大値」の最小値

今から与えられる $Q$ 個のクエリにそれぞれ答えてください。$j$ 番目のクエリは以下の通りです。

• $A_j,S_j,T_j$ が与えられる。辺 $A_j$ の重みを $1$ 増やすと $d(S_j,T_j)$ がいくつ変化するか求めよ。

なお、各クエリにおいて実際には辺の重みは変更しないことに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $U_1$ $V_1$ $W_1$ $\vdots$ $U_M$ $V_M$ $W_M$ $Q$ $A_1$ $S_1$ $T_1$ $\vdots$ $A_Q$ $S_Q$ $T_Q$

输出格式

$Q$ 行出力せよ。 $j\ (1\leq\ j\ \leq\ Q)$ 行目には、$j$ 番目のクエリに対する答えを出力せよ。

题目大意

给一张 $n$ 个点 $m$ 条边的带权无向图，$q$ 组询问，每次给 $(a,x,y)$ 问让第 $a$ 条边边权加一后 $(x,y)$ 的最小瓶颈路变没变。

记某条从 $x$ 到 $y$ 的路径上经过的边权最大的边的边权为 $w$。$(x, y)$ 的最小瓶颈路，指所有 $x$ 到 $y$ 的路径中 $w$ 最小的那条路径对应的 $w$ 值。

$n,m,q\le 2\times 10^5$。

每组询问互相独立。

6 6
1 2 1
3 1 5
4 1 5
3 4 3
5 6 4
2 6 5
7
1 4 6
2 4 6
3 4 6
4 4 6
5 4 6
6 4 6
5 6 5

0
0
0
0
0
1
1

2 2
1 2 1
1 2 1
1
1 1 2

0

提示

制約

• $2\leq\ N\ \leq\ 2\times\ 10^5$
• $N-1\leq\ M\ \leq\ 2\times\ 10^5$
• $1\ \leq\ U_i,V_i\ \leq\ N$
• $U_i\ \neq\ V_i$
• $1\ \leq\ W_i\ \leq\ M$
• 与えられるグラフは連結
• $1\leq\ Q\ \leq\ 2\times\ 10^5$
• $1\ \leq\ A_j\ \leq\ M$
• $1\ \leq\ S_j,T_j\ \leq\ N$
• $S_j\neq\ T_j$
• 入力は全て整数

Sample Explanation 1

上の図においては、辺の番号を黒字で、辺の重みを青字で表記しています。 $1$ 番目から $6$ 番目のクエリについて説明します。 まず与えられたグラフにおける $d(4,6)$ について考えます。 $ 4\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 6 $ というパス上の辺の重みの最大値は $5$ ですが、 これは頂点 $4$ と頂点 $6$ を結ぶパスの中での最小値であるため、$d(4,6)=5$ です。 次に、辺 $x\ (1\ \leq\ x\ \leq\ 6)$ の重みを $1$ 増やすと $d(4,6)$ がいくつ変化するか考えます。 $x=6$ のとき $d(4,6)=6$ となるため変化量は $1$ ですが、$x\ \neq\ 6$ のときは $d(4,6)=5$ となるため変化量は $0$ です。 たとえば $x=3$ のとき、$ 4\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 6 $ というパス上の辺の重みの最大値は $6$ になりますが、 $ 4\ \rightarrow\ 3\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 6 $ というパス上の辺の重みの最大値が $5$ であるため $d(4,6)$ は変わらず $5$ のままです。

Sample Explanation 2

与えられるグラフは多重辺を含むこともあります。