B. Friends

一天，Igor K. 停止了编程，转而研究数学。一个深秋的夜晚，他坐在桌边读书，陷入沉思。 书中的一句话引起了他注意：“在任意六个人中，要么存在三个人两两相识，要么存在三个人两两互不相识。” Igor 无法理解为何所需的最小人数是六人。“五个人也是一样啊！”他不断在心里重复着。“比如，取 Max、Ilya、Vova——他们三个人彼此都认识！现在再给 Vova 加上 Dima 和 Oleg——他们之间谁也不认识谁！这数学真是胡说八道！” Igor K. 找来了他的五个朋友，并记录了他们之间谁和谁是朋友。现在他想验证：在这五个人中，是否一定存在三个人两两相识，或者三个人两两互不相识。 第一行包含一个整数 $m$ $ (0 ≤ m ≤ 10) $，表示 Igor 的五个朋友之间相识关系的数量。 接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $ (1 ≤ a_i, b_i ≤ 5; a_i ≠ b_i) $，表示一对相识的人。保证每对相识关系仅出现一次。相识关系是对称的，即如果 $x$ 认识 $y$，那么 $y$ 也认识 $x$。 如果这五个人中既不存在三个人两两相识，也不存在三个人两两互不相识，则输出 "_FAIL_"；否则输出 "_WIN_"。 ## Input 第一行包含一个整数 $m$ $ (0 ≤ m ≤ 10) $，表示 Igor 的五个朋友之间相识关系的数量。接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $ (1 ≤ a_i, b_i ≤ 5; a_i ≠ b_i) $，表示一对相识的人。保证每对相识关系仅出现一次。相识关系是对称的，即如果 $x$ 认识 $y$，那么 $y$ 也认识 $x$。 ## Output 如果这五个人中既不存在三个人两两相识，也不存在三个人两两互不相识，则输出 "_FAIL_"；否则输出 "_WIN_"。 [samples]

Let $ G = (V, E) $ be an undirected graph with $ |V| = 5 $ vertices, representing Igor’s five friends. Let $ E \subseteq \binom{V}{2} $ be the set of edges, where each edge $ \{a_i, b_i\} \in E $ denotes an acquaintance relation. Let $ \bar{G} = (V, \binom{V}{2} \setminus E) $ be the complement graph, representing unacquainted pairs. Define: - A **clique of size 3** in $ G $: three vertices all pairwise connected by edges in $ E $. - 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} $. **Objective**: Determine whether $ G $ contains either a clique of size 3 or an independent set of size 3. If such a subset exists, output `"WIN"`. Otherwise, output `"FAIL"`. This 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 $. Thus, **"FAIL"** is only possible if the input graph violates the premise — but mathematically, **no such 5-vertex graph exists without a monochromatic triangle**. Hence, the output is always `"WIN"` for any input. But per problem statement: we are to check the given graph. **Formal Decision Rule**: Output `"WIN"` if $ \exists \{u,v,w\} \subseteq V $ such that either: - $ \{u,v\}, \{v,w\}, \{w,u\} \in E $ (triangle in $ G $), or - $ \{u,v\}, \{v,w\}, \{w,u\} \notin E $ (triangle in $ \bar{G} $). Output `"FAIL"` otherwise. However, by Ramsey’s theorem, **no such 5-vertex graph avoids both**. So `"FAIL"` is mathematically impossible. But the problem asks to check the input. Thus, algorithmically: - Given $ m $ edges among 5 vertices, construct adjacency matrix or list. - Enumerate all $ \binom{5}{3} = 10 $ triples of vertices. - For each triple $ \{i,j,k\} $, count the number of edges among them in $ G $. - If the count is 0 → independent set of size 3 → WIN. - If the count is 3 → clique of size 3 → WIN. - If for all 10 triples, the count is 1 or 2 → FAIL. But again, Ramsey’s theorem says this cannot happen. Nonetheless, per problem specification, implement the check. **Final Formal Statement**: Let $ V = \{1,2,3,4,5\} $, and $ E \subseteq \binom{V}{2} $ with $ |E| = m $. Let $ \mathcal{T} = \{ T \subseteq V : |T| = 3 \} $, $ |\mathcal{T}| = 10 $. For each $ T = \{a,b,c\} \in \mathcal{T} $, define: $$ e_T = |\{ \{x,y\} \in E : x,y \in T \}| $$ Then: $$ \text{Output} = \begin{cases} \texttt{"WIN"} & \text{if } \exists T \in \mathcal{T} \text{ such that } e_T = 0 \text{ or } e_T = 3 \\ \texttt{"FAIL"} & \text{otherwise} \end{cases} $$