{"problem":{"name":"A. Bear and Friendship Condition","description":{"content":"Bear Limak examines a social network. Its main functionality is that two members can become friends (then they can talk with each other and share funny pictures). There are _n_ members, numbered 1 th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF771A"},"statements":[{"statement_type":"Markdown","content":"Bear Limak examines a social network. Its main functionality is that two members can become friends (then they can talk with each other and share funny pictures).\n\nThere are _n_ members, numbered 1 through _n_. _m_ pairs of members are friends. Of course, a member can't be a friend with themselves.\n\nLet _A-B_ denote that members _A_ and _B_ are friends. Limak thinks that a network is _reasonable_ if and only if the following condition is satisfied: For every three **distinct** members (_X_, _Y_, _Z_), if _X-Y_ and _Y-Z_ then also _X-Z_.\n\nFor example: if Alan and Bob are friends, and Bob and Ciri are friends, then Alan and Ciri should be friends as well.\n\nCan you help Limak and check if the network is reasonable? Print \"_YES_\" or \"_NO_\" accordingly, without the quotes.\n\n## Input\n\nThe first line of the input contain two integers _n_ and _m_ (3 ≤ _n_ ≤ 150 000, ) — the number of members and the number of pairs of members that are friends.\n\nThe _i_\\-th of the next _m_ lines contains two distinct integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_). Members _a__i_ and _b__i_ are friends with each other. No pair of members will appear more than once in the input.\n\n## Output\n\nIf the given network is reasonable, print \"_YES_\" in a single line (without the quotes). Otherwise, print \"_NO_\" in a single line (without the quotes).\n\n[samples]\n\n## Note\n\nThe drawings below show the situation in the first sample (on the left) and in the second sample (on the right). Each edge represents two members that are friends. The answer is \"_NO_\" in the second sample because members (2, 3) are friends and members (3, 4) are friends, while members (2, 4) are not.\n\n<center>![image](https://espresso.codeforces.com/999abd3a2ce8ac1986b5396a1ab1d24150213635.png)</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Bear Limak 检查一个社交网络。其主要功能是两个成员可以成为朋友（之后他们可以互相交谈并分享有趣的照片）。\n\n共有 #cf_span[n] 个成员，编号为 #cf_span[1] 到 #cf_span[n]。有 #cf_span[m] 对成员是朋友。当然，一个成员不能与自己成为朋友。\n\n用 _A-B_ 表示成员 _A_ 和 _B_ 是朋友。Limak 认为，当且仅当满足以下条件时，该网络是 _合理的_：对于任意三个 _互不相同_ 的成员 (_X_, _Y_, _Z_)，如果 _X-Y_ 且 _Y-Z_，那么也必须有 _X-Z_。\n\n例如：如果 Alan 和 Bob 是朋友，Bob 和 Ciri 是朋友，那么 Alan 和 Ciri 也应该是朋友。\n\n你能帮助 Limak 检查该网络是否合理吗？请相应地输出 \"_YES_\" 或 \"_NO_\"（不含引号）。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[3 ≤ n ≤ 150 000]）——成员数量和朋友对的数量。\n\n接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含两个互不相同的整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n, ai ≠ bi]）。成员 #cf_span[ai] 和 #cf_span[bi] 互为朋友。输入中不会出现重复的成员对。\n\n如果给定的网络是合理的，请在单独一行输出 \"_YES_\"（不含引号）；否则，输出 \"_NO_\"（不含引号）。\n\n下图展示了第一个样例（左）和第二个样例（右）的情况。每条边代表一对朋友。第二个样例的答案是 \"_NO_\"，因为成员 #cf_span[(2, 3)] 是朋友，成员 #cf_span[(3, 4)] 是朋友，但成员 #cf_span[(2, 4)] 不是朋友。\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[3 ≤ n ≤ 150 000]）——成员数量和朋友对的数量。第 #cf_span[i] 行是接下来的 #cf_span[m] 行之一，包含两个互不相同的整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n, ai ≠ bi]）。成员 #cf_span[ai] 和 #cf_span[bi] 互为朋友。输入中不会出现重复的成员对。\n\n## Output\n\n如果给定的网络是合理的，请在单独一行输出 \"_YES_\"（不含引号）；否则，输出 \"_NO_\"（不含引号）。\n\n[samples]\n\n## Note\n\n下图展示了第一个样例（左）和第二个样例（右）的情况。每条边代表一对朋友。第二个样例的答案是 \"_NO_\"，因为成员 #cf_span[(2, 3)] 是朋友，成员 #cf_span[(3, 4)] 是朋友，但成员 #cf_span[(2, 4)] 不是朋友。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $ vertices and $ |E| = m $ edges, where each vertex represents a member and each edge represents a friendship.\n\n**Constraints**  \n1. $ 3 \\leq n \\leq 150{,}000 $  \n2. $ 0 \\leq m \\leq \\binom{n}{2} $  \n3. No self-loops or multiple edges: $ \\forall (u,v) \\in E, u \\ne v $ and all edges are distinct.\n\n**Objective**  \nDetermine whether $ G $ satisfies the *transitivity condition*:  \nFor all distinct vertices $ x, y, z \\in V $, if $ (x,y) \\in E $ and $ (y,z) \\in E $, then $ (x,z) \\in E $.\n\nOutput \"YES\" if the condition holds for all such triples; otherwise, output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF771A","tags":["dfs and similar","dsu","graphs"],"sample_group":[["4 3\n1 3\n3 4\n1 4","YES"],["4 4\n3 1\n2 3\n3 4\n1 2","NO"],["10 4\n4 3\n5 10\n8 9\n1 2","YES"],["3 2\n1 2\n2 3","NO"]],"created_at":"2026-03-03 11:00:39"}}