题目描述

$N$ 頂点 $M$ 辺の重み付き無向連結グラフ $G$ が与えられます。$G$ には自己ループや多重辺が含まれている可能性があります。
頂点には頂点 $1$, 頂点 $2$, $\dots$, 頂点 $N$ と番号がついています。
辺には辺 $1$, 辺 $2$, $\dots$, 辺 $M$ と番号がついています。辺 $i$ は頂点 $a_i$ と頂点 $b_i$ を結ぶ重み $c_i$ の辺です。ここで、$1\ \leq\ i\ \lt\ j\ \leq\ M$ を満たすすべての整数の組 $(i,\ j)$ について $c_i\ \neq\ c_j$ が成り立ちます。

以下で説明される $Q$ 個のクエリに答えてください。
$i$ 番目のクエリでは整数の組 $(u_i,\ v_i,\ w_i)$ が与えられます。ここで、$1\ \leq\ j\ \leq\ M$ を満たすすべての整数 $j$ について $w_i\ \neq\ c_j$ が成り立ちます。
頂点 $u_i$ と頂点 $v_i$ を結ぶ重み $w_i$ の無向辺を $e_i$ として、$G$ に $e_i$ を追加してできるグラフ $G_i$ を考えます。 このとき $G_i$ の最小全域木 $T_i$ は一意に定まることが証明できますが、$T_i$ に $e_i$ は含まれるでしょうか？答えを Yes あるいは No で出力してください。

ここで、クエリの前後で $G$ は変化しないことに注意してください。言い換えると、クエリ $i$ で $G$ に $e_i$ を追加したグラフを考えたとしても、他のクエリで出てくる $G$ に $e_i$ が追加されていることはありません。

最小全域木とは？ $G$ の 全域木 とは、$G$ に含まれるすべての頂点と $G$ に含まれる辺の一部からなる木のことを言います。
$G$ の 最小全域木 とは、$G$ の全域木の中で辺の重みの和が最小である木のことを言います。

输入格式

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

$N$ $M$ $Q$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $\vdots$ $a_M$ $b_M$ $c_M$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $\vdots$ $u_Q$ $v_Q$ $w_Q$

输出格式

$Q$ 行出力せよ。$i$ 行目ではクエリ $i$ への答えを Yes または No で出力せよ。

题目大意

给定一个 $n$ 个点，$m$ 条边无向连通图，每条边有权值 $c_i$，各不相同

所以，其最小生成树是唯一的。

有 $q$ 次询问，每次给出一条边：$x_i, y_i, w_i$

表示两端点为 $x_i$ 和 $y_i$ ，权值为 $w_i$

问：加入这条边之后，该图的最小生成树会不会发生变化？

或者说，加入的这条边是否会在新的最小生成树中？

5 6 3
1 2 2
2 3 3
1 3 6
2 4 5
4 5 9
3 5 8
1 3 1
3 4 7
3 5 7

Yes
No
Yes

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Yes
No

提示

制約

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $N\ -\ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ a_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ M)$
• $1\ \leq\ b_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ M)$
• $1\ \leq\ c_i\ \leq\ 10^9$ $(1\ \leq\ i\ \leq\ M)$
• $c_i\ \neq\ c_j$ $(1\ \leq\ i\ \lt\ j\ \leq\ M)$
• グラフ $G$ は連結である。
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ u_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ Q)$
• $1\ \leq\ v_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ Q)$
• $1\ \leq\ w_i\ \leq\ 10^9$ $(1\ \leq\ i\ \leq\ Q)$
• $w_i\ \neq\ c_j$ $(1\ \leq\ i\ \leq\ Q,\ 1\ \leq\ j\ \leq\ M)$
• 入力はすべて整数である。

Sample Explanation 1

以下では頂点 $u$ と頂点 $v$ を結ぶ重み $w$ の無向辺を $(u,v,w)$ と表します。 $G$ を図に表したものを以下に挙げます。  たとえばクエリ $1$ では $G$ に $e_1\ =\ (1,3,1)$ を追加したグラフ $G_1$ を考えます。$G_1$ の最小全域木 $T_1$ の辺集合は $ \lbrace\ (1,2,2),(1,3,1),(2,4,5),(3,5,8)\ \rbrace $ であり $e_1$ を含みます。よって Yes を出力します。