102354: [AtCoder]ABC235 E - MST + 1

Problem Statement

Given is a weighted undirected connected graph $G$ with $N$ vertices and $M$ edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex $1$, Vertex $2$, $\dots$, Vertex $N$.
The edges are labeled as Edge $1$, Edge $2$, $\ldots$, Edge $M$. Edge $i$ connects Vertex $a_i$ and Vertex $b_i$ and has a weight of $c_i$. Here, for every pair of integers $(i, j)$ such that $1 \leq i \lt j \leq M$, $c_i \neq c_j$ holds.

Process the $Q$ queries explained below.
The $i$-th query gives a triple of integers $(u_i, v_i, w_i)$. Here, for every integer $j$ such that $1 \leq j \leq M$, $w_i \neq c_j$ holds.
Let $e_i$ be an undirected edge that connects Vertex $u_i$ and Vertex $v_i$ and has a weight of $w_i$. Consider the graph $G_i$ obtained by adding $e_i$ to $G$. It can be proved that the minimum spanning tree $T_i$ of $G_i$ is uniquely determined. Does $T_i$ contain $e_i$? Print the answer as Yes or No.

Note that the queries do not change $T$. In other words, even though Query $i$ considers the graph obtained by adding $e_i$ to $G$, the $G$ in other queries does not have $e_i$.

Constraints

• $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)$
• The graph $G$ is connected.
• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line should contain the answer to Query $i$: Yes or No.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

Below, let $(u,v,w)$ denote an undirected edge that connects Vertex $u$ and Vertex $v$ and has the weight of $w$. Here is an illustration of $G$:

For example, Query $1$ considers the graph $G_1$ obtained by adding $e_1 = (1,3,1)$ to $G$. The minimum spanning tree $T_1$ of $G_1$ has the edge set $\lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace$, which contains $e_1$, so Yes should be printed.

Sample Input 2

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

Sample Output 2

Yes
No

问题描述

给定一个带有权重的无向连通图$G$，它可能包含自环和多边形。顶点标记为顶点$1$，顶点$2$，$\dots$，顶点$N$。边标记为边$1$，边$2$，$\ldots$，边$M$。边$i$连接顶点$a_i$和顶点$b_i$，权重为$c_i$。在这里，对于每一对整数$(i, j)$，满足$1 \leq i \lt j \leq M$时，$c_i \neq c_j$成立。

处理以下解释的$Q$查询。第$i$个查询给出一个整数三元组$(u_i, v_i, w_i)$。在这里，对于满足$1 \leq j \leq M$的每个整数$j$，$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。

样例输入1

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

样例输出1

Yes
No
Yes

下面是$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

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

样例输出2

Yes
No