对于连通无向带权图 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 的环,因此不存在包含这三个边的生成树。因此,答案是“否”。