AT_abc235_e [ABC235E] MST + 1

[problemUrl]: https://atcoder.jp/contests/abc235/tasks/abc235_e $ 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` で出力せよ。

### 制約 - $ 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 $ を図に表したものを以下に挙げます。 !\[image\](https://img.atcoder.jp/ghi/15ac15edee5a8b055f65192d7323d43b.png) たとえばクエリ $ 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` を出力します。