E-MST + 1

得分：500分

问题描述

给定一个带有N个顶点和M条边的加权无向连通图G，其中可能包含自环和重边。
顶点被标记为顶点1,顶点2, ..., 顶点N。
边被标记为边1,边2, ..., 边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)$。对于每个整数j满足$1 \leq j \leq M$，满足$w_i \neq c_j$。
令$e_i$是连接顶点$u_i$和$v_i$并具有权重$w_i$的无向边。考虑通过将$e_i$添加到G后得到的图$G_i$。 可以证明，$G_i$的最小生成树$T_i$是唯一确定的。$T_i$包含$e_i$吗？以“Yes”或“No”打印答案。

注意，查询不会改变T。换句话说，即使查询$i$考虑了通过将$e_i$添加到G得到的图，其他查询中的G也不包含$e_i$。

约束条件

• $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)$
• 输入中的所有值都是整数。

输入

从标准输入中以如下格式给出：

$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”。

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

下面，令$(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”。

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

Yes
No