{"problem":{"name":"D. Almost Acyclic Graph","description":{"content":"You are given a [directed graph](https://en.wikipedia.org/wiki/Directed_graph) consisting of _n_ vertices and _m_ edges (each edge is directed, so it can be traversed in only one direction). You are a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF915D"},"statements":[{"statement_type":"Markdown","content":"You are given a [directed graph](https://en.wikipedia.org/wiki/Directed_graph) consisting of _n_ vertices and _m_ edges (each edge is directed, so it can be traversed in only one direction). You are allowed to remove at most one edge from it.\n\nCan you make this graph [acyclic](https://en.wikipedia.org/wiki/Directed_acyclic_graph) by removing at most one edge from it? A directed graph is called acyclic iff it doesn't contain any cycle (a non-empty path that starts and ends in the same vertex).\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 500, 1 ≤ _m_ ≤ _min_(_n_(_n_ - 1), 100000)) — the number of vertices and the number of edges, respectively.\n\nThen _m_ lines follow. Each line contains two integers _u_ and _v_ denoting a directed edge going from vertex _u_ to vertex _v_ (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_). Each ordered pair (_u_, _v_) is listed at most once (there is at most one directed edge from _u_ to _v_).\n\n## Output\n\nIf it is possible to make this graph acyclic by removing at most one edge, print _YES_. Otherwise, print _NO_.\n\n[samples]\n\n## Note\n\nIn the first example you can remove edge , and the graph becomes acyclic.\n\nIn the second example you have to remove at least two edges (for example, and ) in order to make the graph acyclic.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边（每条边都是有向的，只能沿一个方向遍历）。你可以最多删除其中一条边。\n\n能否通过删除至多一条边使该图变为无环图？一个有向图被称为无环图，当且仅当其中不包含任何环（一个非空路径，起点和终点为同一顶点）。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 500]，#cf_span[1 ≤ m ≤ min(n(n - 1), 100000)]）——分别表示顶点数和边数。\n\n接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]，表示一条从顶点 #cf_span[u] 指向顶点 #cf_span[v] 的有向边（#cf_span[1 ≤ u, v ≤ n]，#cf_span[u ≠ v]）。每个有序对 #cf_span[(u, v)] 最多出现一次（从 #cf_span[u] 到 #cf_span[v] 的有向边至多一条）。\n\n如果可以通过删除至多一条边使该图变为无环图，则输出 _YES_；否则输出 _NO_。\n\n在第一个示例中，你可以删除边 ，图将变为无环图。\n\n在第二个示例中，你必须删除至少两条边（例如， 和 ）才能使图变为无环图。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 500]，#cf_span[1 ≤ m ≤ min(n(n - 1), 100000)]）——分别表示顶点数和边数。接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]，表示一条从顶点 #cf_span[u] 指向顶点 #cf_span[v] 的有向边（#cf_span[1 ≤ u, v ≤ n]，#cf_span[u ≠ v]）。每个有序对 #cf_span[(u, v)] 最多出现一次（从 #cf_span[u] 到 #cf_span[v] 的有向边至多一条）。\n\n## Output\n\n如果可以通过删除至多一条边使该图变为无环图，则输出 _YES_；否则输出 _NO_。\n\n[samples]\n\n## Note\n\n在第一个示例中，你可以删除边 ，图将变为无环图。在第二个示例中，你必须删除至少两条边（例如， 和 ）才能使图变为无环图。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $.\n\n**Goal:** Determine whether there exists an edge $ e \\in E $ such that the graph $ G' = (V, E \\setminus \\{e\\}) $ is acyclic, or whether $ G $ is already acyclic (i.e., remove zero edges).\n\n**Formal Statement:**\n\nDoes there exist a subset $ E' \\subseteq E $ with $ |E'| \\leq 1 $ such that $ (V, E \\setminus E') $ is a directed acyclic graph (DAG)?\n\nEquivalently:\n\n- If $ G $ is already acyclic, return YES.\n- Else, for each edge $ e \\in E $, check whether $ G \\setminus \\{e\\} $ is acyclic. If any such $ G \\setminus \\{e\\} $ is acyclic, return YES; otherwise, return NO.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF915D","tags":["dfs and similar","graphs"],"sample_group":[["3 4\n1 2\n2 3\n3 2\n3 1","YES"],["5 6\n1 2\n2 3\n3 2\n3 1\n2 1\n4 5","NO"]],"created_at":"2026-03-03 11:00:39"}}