← 返回题目列表

Codeforces · 891/C

C. 羡慕

中文机器翻译题面 查看原题

对于连通无向带权图 G,MST(最小生成树)是 G 的子图,包含 G 的所有顶点,是一棵树,且其边之和尽可能最小。

给你一个图 G。如果你在图上运行 MST 算法,它只会给你一个 MST,并导致其他边变得嫉妒。给你一些查询,每个查询包含图 G 的一组边,你应该确定是否存在包含所有这些边的 MST。

输入

第一行包含两个整数 n, m (2 ≤ n, m ≤ 5·105, n - 1 ≤ m) - 图中的顶点和边的数量以及查询的数量。

接下来 m 行的第 i 行包含三个整数 ui, vi, wi (ui ≠ vi, 1 ≤ wi ≤ 5·105) - 第 i 条边的端点和权重。两个顶点之间可以有多条边。保证给定的图是连通的。

下一行包含一个整数 q (1 ≤ q ≤ 5·105) — 查询数。

q 行如下,其中第 i 行包含第 i 个查询。它以整数 ki (1 ≤ ki ≤ n - 1) — 边子集的大小开始,并以 ki 个不同的空格分隔整数从 1 到 m — 边的索引继续。保证1 ≤ i ≤ q 的ki 之和不超过5·105。

输出

对于每个查询,如果存在包含这些边的 MST,则应打印“YES”(不带引号),否则应打印“NO”(当然再次不带引号)。

示例

输入 #1

5 7
1 2 2
1 3 2
2 3 1
2 4 1
3 4 1
3 5 2
4 5 2
4
2 3 4
3 3 4 5
2 1 7
2 1 2

输出 #1

YES
NO
YES
NO

注意

这是样本图:

该图上最小生成树的权重为 6。

具有边 (1, 3, 4, 6) 的 MST,包含第一个查询的所有边,因此第一个查询的答案是“是”。

第二个查询的边形成长度为 3 的环,因此不存在包含这三个边的生成树。因此,答案是“否”。