题目描述

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

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

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

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

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

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

输入格式

第一行输入三个整数 $n,m,q$

接下来 $m$ 行每行三个整数代表 $u,v,w$

接下来 $q$ 行每行三个整数代表 $x,y,w$

输出格式

输出一共输出 $q$ 行针对每次询问输出 Yes 或 No

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)$
• $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$ 考虑了将 $e_1 = (1,3,1)$ 添加到 $G$ 后得到的图 $G_1$ 。 $G_1$ 的最小生成树 $T_1$ 的边集 $\lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace$ 包含 $e_1$ ，因此应打印 Yes