#P5609. Envy

    ID: 4610 传统题 1000ms 256MiB 尝试: 27 已通过: 6 难度: 6 上传者: 标签>CF2100提高+/省选-Kruskal可撤销并查集按大小合并离线查询查询排序树论

Envy

Description

给出一个n个点m条边的无向图,每条边有边权.

共Q次询问,每次给出ki条边,问这些边能否同时在一棵最小生成树上。

Format

Input

第一行两个整数 N,MN,M,分别表示顶点数和边数。2≤N≤5×1052\le N\le 5\times10^5,N−1≤M≤5×105N-1\le M\le5\times10^5。

接下来 MM 行,第 ii 行给出边 ii 的端点 ui,viu_i,v_i 和权值 wiw_i。1≤ui,vi≤N1\le u_i,v_i\le N,ui≠viu_i\ne v_i,1≤wi≤5×1051\le w_i\le5\times10^5。允许重边,保证图连通。

接下来一行整数 QQ(1≤Q≤5×1051\le Q\le5\times10^5)。每次询问先给出 kik_i(1≤ki≤N−11\le k_i\le N-1),再给出 kik_i 个互不相同的边编号,范围为 11 到 MM。保证 ∑i=1Qki≤5×105\sum_{i=1}^{Q}k_i\le5\times10^5。

Output

输出Q行

针对每组询问,输出“YES”或“NO”

Samples

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
YES
NO
YES
NO