{"problem":{"name":"B. Friends","description":{"content":"One day Igor K. stopped programming and took up math. One late autumn evening he was sitting at a table reading a book and thinking about something. The following statement caught his attention: \"Amo","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF94B"},"statements":[{"statement_type":"Markdown","content":"One day Igor K. stopped programming and took up math. One late autumn evening he was sitting at a table reading a book and thinking about something.\n\nThe following statement caught his attention: \"Among any six people there are either three pairwise acquainted people or three pairwise unacquainted people\"\n\nIgor just couldn't get why the required minimum is 6 people. \"Well, that's the same for five people, too!\" — he kept on repeating in his mind. — \"Let's take, say, Max, Ilya, Vova — here, they all know each other! And now let's add Dima and Oleg to Vova — none of them is acquainted with each other! Now, that math is just rubbish!\"\n\nIgor K. took 5 friends of his and wrote down who of them is friends with whom. Now he wants to check whether it is true for the five people that among them there are either three pairwise acquainted or three pairwise not acquainted people.\n\n## Input\n\nThe first line contains an integer _m_ (0 ≤ _m_ ≤ 10), which is the number of relations of acquaintances among the five friends of Igor's.\n\nEach of the following _m_ lines contains two integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ 5;_a__i_ ≠ _b__i_), where (_a__i_, _b__i_) is a pair of acquainted people. It is guaranteed that each pair of the acquaintances is described exactly once. The acquaintance relation is symmetrical, i.e. if _x_ is acquainted with _y_, then _y_ is also acquainted with _x_.\n\n## Output\n\nPrint \"_FAIL_\", if among those five people there are no either three pairwise acquainted or three pairwise unacquainted people. Otherwise print \"_WIN_\".\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一天，Igor K. 停止了编程，转而研究数学。一个深秋的夜晚，他坐在桌边读书，陷入沉思。\n\n书中的一句话引起了他注意：“在任意六个人中，要么存在三个人两两相识，要么存在三个人两两互不相识。”\n\nIgor 无法理解为何所需的最小人数是六人。“五个人也是一样啊！”他不断在心里重复着。“比如，取 Max、Ilya、Vova——他们三个人彼此都认识！现在再给 Vova 加上 Dima 和 Oleg——他们之间谁也不认识谁！这数学真是胡说八道！”\n\nIgor K. 找来了他的五个朋友，并记录了他们之间谁和谁是朋友。现在他想验证：在这五个人中，是否一定存在三个人两两相识，或者三个人两两互不相识。\n\n第一行包含一个整数 $m$ $ (0 ≤ m ≤ 10) $，表示 Igor 的五个朋友之间相识关系的数量。\n\n接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $ (1 ≤ a_i, b_i ≤ 5; a_i ≠ b_i) $，表示一对相识的人。保证每对相识关系仅出现一次。相识关系是对称的，即如果 $x$ 认识 $y$，那么 $y$ 也认识 $x$。\n\n如果这五个人中既不存在三个人两两相识，也不存在三个人两两互不相识，则输出 \"_FAIL_\"；否则输出 \"_WIN_\"。\n\n## Input\n\n第一行包含一个整数 $m$ $ (0 ≤ m ≤ 10) $，表示 Igor 的五个朋友之间相识关系的数量。接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $ (1 ≤ a_i, b_i ≤ 5; a_i ≠ b_i) $，表示一对相识的人。保证每对相识关系仅出现一次。相识关系是对称的，即如果 $x$ 认识 $y$，那么 $y$ 也认识 $x$。\n\n## Output\n\n如果这五个人中既不存在三个人两两相识，也不存在三个人两两互不相识，则输出 \"_FAIL_\"；否则输出 \"_WIN_\"。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ G = (V, E) $ be an undirected graph with $ |V| = 5 $ vertices, representing Igor’s five friends.  \nLet $ E \\subseteq \\binom{V}{2} $ be the set of edges, where each edge $ \\{a_i, b_i\\} \\in E $ denotes an acquaintance relation.  \nLet $ \\bar{G} = (V, \\binom{V}{2} \\setminus E) $ be the complement graph, representing unacquainted pairs.\n\nDefine:  \n- A **clique of size 3** in $ G $: three vertices all pairwise connected by edges in $ E $.  \n- An **independent set of size 3** in $ G $: three vertices with no edges between them in $ E $, i.e., a clique of size 3 in $ \\bar{G} $.\n\n**Objective**:  \nDetermine whether $ G $ contains either a clique of size 3 or an independent set of size 3.\n\nIf such a subset exists, output `\"WIN\"`.  \nOtherwise, output `\"FAIL\"`.\n\nThis is equivalent to checking whether the Ramsey number $ R(3,3) > 5 $, which is false — since $ R(3,3) = 6 $, every 2-coloring of $ K_5 $ contains a monochromatic $ K_3 $.  \nThus, **\"FAIL\"** is only possible if the input graph violates the premise — but mathematically, **no such 5-vertex graph exists without a monochromatic triangle**.  \nHence, the output is always `\"WIN\"` for any input.\n\nBut per problem statement: we are to check the given graph.\n\n**Formal Decision Rule**:  \nOutput `\"WIN\"` if $ \\exists \\{u,v,w\\} \\subseteq V $ such that either:  \n- $ \\{u,v\\}, \\{v,w\\}, \\{w,u\\} \\in E $ (triangle in $ G $), or  \n- $ \\{u,v\\}, \\{v,w\\}, \\{w,u\\} \\notin E $ (triangle in $ \\bar{G} $).  \n\nOutput `\"FAIL\"` otherwise.\n\nHowever, by Ramsey’s theorem, **no such 5-vertex graph avoids both**.  \nSo `\"FAIL\"` is mathematically impossible. But the problem asks to check the input.\n\nThus, algorithmically:\n\n- Given $ m $ edges among 5 vertices, construct adjacency matrix or list.\n- Enumerate all $ \\binom{5}{3} = 10 $ triples of vertices.\n- For each triple $ \\{i,j,k\\} $, count the number of edges among them in $ G $.\n- If the count is 0 → independent set of size 3 → WIN.\n- If the count is 3 → clique of size 3 → WIN.\n- If for all 10 triples, the count is 1 or 2 → FAIL.\n\nBut again, Ramsey’s theorem says this cannot happen.\n\nNonetheless, per problem specification, implement the check.\n\n**Final Formal Statement**:\n\nLet $ V = \\{1,2,3,4,5\\} $, and $ E \\subseteq \\binom{V}{2} $ with $ |E| = m $.  \nLet $ \\mathcal{T} = \\{ T \\subseteq V : |T| = 3 \\} $, $ |\\mathcal{T}| = 10 $.  \nFor each $ T = \\{a,b,c\\} \\in \\mathcal{T} $, define:  \n$$\ne_T = |\\{ \\{x,y\\} \\in E : x,y \\in T \\}|\n$$\n\nThen:  \n$$\n\\text{Output} =\n\\begin{cases}\n\\texttt{\"WIN\"} & \\text{if } \\exists T \\in \\mathcal{T} \\text{ such that } e_T = 0 \\text{ or } e_T = 3 \\\\\n\\texttt{\"FAIL\"} & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF94B","tags":["graphs","implementation","math"],"sample_group":[["4\n1 3\n2 3\n1 4\n5 3","WIN"],["5\n1 2\n2 3\n3 4\n4 5\n5 1","FAIL"]],"created_at":"2026-03-03 11:00:39"}}