{"problem":{"name":"C. Envy","description":{"content":"For a connected undirected weighted graph _G_, MST (minimum spanning tree) is a subgraph of _G_ that contains all of _G_'s vertices, is a tree, and sum of its edges is minimum possible. You are given","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF891C"},"statements":[{"statement_type":"Markdown","content":"For a connected undirected weighted graph _G_, MST (minimum spanning tree) is a subgraph of _G_ that contains all of _G_'s vertices, is a tree, and sum of its edges is minimum possible.\n\nYou are given a graph _G_. If you run a MST algorithm on graph it would give you only one MST and it causes other edges to become jealous. You are given some queries, each query contains a set of edges of graph _G_, and you should determine whether there is a MST containing all these edges or not.\n\n## Input\n\nThe first line contains two integers _n_, _m_ (2  ≤ _n_, _m_  ≤ 5·105, _n_ - 1 ≤ _m_) — the number of vertices and edges in the graph and the number of queries.\n\nThe _i_\\-th of the next _m_ lines contains three integers _u__i_, _v__i_, _w__i_ (_u__i_ ≠ _v__i_, 1 ≤ _w__i_ ≤ 5·105) — the endpoints and weight of the _i_\\-th edge. There can be more than one edges between two vertices. It's guaranteed that the given graph is connected.\n\nThe next line contains a single integer _q_ (1 ≤ _q_ ≤ 5·105) — the number of queries.\n\n_q_ lines follow, the _i_\\-th of them contains the _i_\\-th query. It starts with an integer _k__i_ (1 ≤ _k__i_ ≤ _n_ - 1) — the size of edges subset and continues with _k__i_ distinct space-separated integers from 1 to _m_ — the indices of the edges. It is guaranteed that the sum of _k__i_ for 1 ≤ _i_ ≤ _q_ does not exceed 5·105.\n\n## Output\n\nFor each query you should print \"_YES_\" (without quotes) if there's a MST containing these edges and \"_NO_\" (of course without quotes again) otherwise.\n\n[samples]\n\n## Note\n\nThis is the graph of sample:\n\n<center>![image](https://espresso.codeforces.com/adbd629e93f96313d6198b2ec6b671cda2f337f8.png)</center>Weight of minimum spanning tree on this graph is 6.\n\nMST with edges (1, 3, 4, 6), contains all of edges from the first query, so answer on the first query is \"_YES_\".\n\nEdges from the second query form a cycle of length 3, so there is no spanning tree including these three edges. Thus, answer is \"_NO_\".","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"对于一个连通无向加权图 #cf_span[G]，最小生成树（MST）是 #cf_span[G] 的一个子图，它包含 #cf_span[G] 的所有顶点，是一棵树，且其边权和最小。\n\n你被给定一个图 #cf_span[G]。当你在该图上运行 MST 算法时，它只会给出一个 MST，并导致其他边变得“嫉妒”。你将收到一些查询，每个查询包含图 #cf_span[G] 的一组边，你需要判断是否存在一个 MST 包含这些所有边。\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2  ≤ n, m  ≤ 5·105], #cf_span[n - 1 ≤ m]) —— 图的顶点数、边数和查询数。\n\n接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi] (#cf_span[ui ≠ vi], #cf_span[1 ≤ wi ≤ 5·105]) —— 第 #cf_span[i] 条边的两个端点及其权重。两个顶点之间可能存在多条边。保证给定的图是连通的。\n\n下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 5·105]) —— 查询数。\n\n接下来 #cf_span[q] 行，第 #cf_span[i] 行包含第 #cf_span[i] 个查询。它以一个整数 #cf_span[ki] (#cf_span[1 ≤ ki ≤ n - 1]) 开头，表示边子集的大小，随后是 #cf_span[ki] 个互不相同的、范围在 #cf_span[1] 到 #cf_span[m] 的空格分隔整数 —— 表示边的编号。保证所有查询的 #cf_span[ki] 之和不超过 #cf_span[5·105]。\n\n对于每个查询，如果存在一个 MST 包含这些边，请输出 \"_YES_\"（不含引号），否则输出 \"_NO_\"（同样不含引号）。\n\n这是样例的图：\n\n该图的最小生成树权重为 #cf_span[6]。\n\n包含边 #cf_span[(1, 3, 4, 6)] 的 MST 包含了第一个查询的所有边，因此第一个查询的答案是 \"_YES_\"。\n\n第二个查询中的边构成一个长度为 #cf_span[3] 的环，因此不存在包含这三条边的生成树，故答案为 \"_NO_\"。\n\n## Input\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2  ≤ n, m  ≤ 5·105], #cf_span[n - 1 ≤ m]) —— 图的顶点数、边数和查询数。第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi] (#cf_span[ui ≠ vi], #cf_span[1 ≤ wi ≤ 5·105]) —— 第 #cf_span[i] 条边的两个端点及其权重。两个顶点之间可能存在多条边。保证给定的图是连通的。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 5·105]) —— 查询数。接下来 #cf_span[q] 行，第 #cf_span[i] 行包含第 #cf_span[i] 个查询。它以一个整数 #cf_span[ki] (#cf_span[1 ≤ ki ≤ n - 1]) 开头，表示边子集的大小，随后是 #cf_span[ki] 个互不相同的、范围在 #cf_span[1] 到 #cf_span[m] 的空格分隔整数 —— 表示边的编号。保证所有查询的 #cf_span[ki] 之和不超过 #cf_span[5·105]。\n\n## Output\n\n对于每个查询，如果存在一个 MST 包含这些边，请输出 \"_YES_\"（不含引号），否则输出 \"_NO_\"（同样不含引号）。\n\n[samples]\n\n## Note\n\n这是样例的图： 该图的最小生成树权重为 #cf_span[6]。包含边 #cf_span[(1, 3, 4, 6)] 的 MST 包含了第一个查询的所有边，因此第一个查询的答案是 \"_YES_\"。第二个查询中的边构成一个长度为 #cf_span[3] 的环，因此不存在包含这三条边的生成树，故答案为 \"_NO_\"。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected weighted graph with $ |V| = n $, $ |E| = m $, and edge weights $ w: E \\to \\mathbb{Z}^+ $.  \nLet $ \\mathcal{M} $ be the set of all minimum spanning trees (MSTs) of $ G $.  \n\n**Constraints**  \n1. $ 2 \\le n, m \\le 5 \\cdot 10^5 $, $ n - 1 \\le m $  \n2. Each edge $ e_i \\in E $ has endpoints $ u_i, v_i \\in V $, $ u_i \\ne v_i $, and weight $ w_i \\in [1, 5 \\cdot 10^5] $  \n3. Multiple edges between same pair of vertices are allowed  \n4. $ G $ is connected  \n5. $ q \\in \\mathbb{Z} $, $ 1 \\le q \\le 5 \\cdot 10^5 $  \n6. For each query $ i $:  \n   - $ k_i \\in \\mathbb{Z} $, $ 1 \\le k_i \\le n - 1 $  \n   - Query $ i $ provides a set $ Q_i \\subseteq E $ of $ k_i $ distinct edge indices  \n   - $ \\sum_{i=1}^q k_i \\le 5 \\cdot 10^5 $  \n\n**Objective**  \nFor each query $ Q_i $, determine whether there exists an MST $ T \\in \\mathcal{M} $ such that $ Q_i \\subseteq T $.  \nOutput \"YES\" if such $ T $ exists, \"NO\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF891C","tags":["data structures","dsu","graphs"],"sample_group":[["5 7\n1 2 2\n1 3 2\n2 3 1\n2 4 1\n3 4 1\n3 5 2\n4 5 2\n4\n2 3 4\n3 3 4 5\n2 1 7\n2 1 2","YES\nNO\nYES\nNO"]],"created_at":"2026-03-03 11:00:39"}}