{"raw_statement":[{"iden":"statement","content":"You are given _n_ switches and _m_ lamps. The _i_\\-th switch turns on some subset of the lamps. This information is given as the matrix _a_ consisting of _n_ rows and _m_ columns where _a__i_, _j_ = 1 if the _i_\\-th switch turns on the _j_\\-th lamp and _a__i_, _j_ = 0 if the _i_\\-th switch is not connected to the _j_\\-th lamp.\n\nInitially all _m_ lamps are turned off.\n\nSwitches change state only from \"off\" to \"on\". It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards.\n\nIt is guaranteed that if you push all _n_ switches then **all _m_ lamps will be turned on**.\n\nYour think that you have too many switches and you would like to ignore one of them.\n\nYour task is to say if there exists such a switch that if you will ignore (not use) it but press all the other _n_ - 1 switches then all the _m_ lamps will be turned on."},{"iden":"input","content":"The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 2000) — the number of the switches and the number of the lamps.\n\nThe following _n_ lines contain _m_ characters each. The character _a__i_, _j_ is equal to '_1_' if the _i_\\-th switch turns on the _j_\\-th lamp and '_0_' otherwise.\n\nIt is guaranteed that if you press all _n_ switches **all _m_ lamps will be turned on**."},{"iden":"output","content":"Print \"_YES_\" if there is a switch that if you will ignore it and press all the other _n_ - 1 switches then all _m_ lamps will be turned on. Print \"_NO_\" if there is no such switch."},{"iden":"examples","content":"Input\n\n4 5\n10101\n01000\n00111\n10000\n\nOutput\n\nYES\n\nInput\n\n4 5\n10100\n01000\n00110\n00101\n\nOutput\n\nNO"}],"translated_statement":[{"iden":"statement","content":"你被给定 #cf_span[n] 个开关和 #cf_span[m] 个灯泡。第 #cf_span[i] 个开关控制某些灯泡的开启。该信息以一个 #cf_span[n] 行 #cf_span[m] 列的矩阵 #cf_span[a] 给出，其中当第 #cf_span[i] 个开关控制第 #cf_span[j] 个灯泡时，#cf_span[ai, j = 1]；否则 #cf_span[ai, j = 0]。\n\n初始时，所有 #cf_span[m] 个灯泡均处于关闭状态。\n\n开关仅能从“关闭”变为“开启”。这意味着，如果两个或多个开关连接到同一个灯泡，则只要按下其中任意一个开关，该灯泡就会被点亮，并且即使之后再按下其他连接到该灯泡的开关，其状态也不会改变。\n\n保证如果按下所有 #cf_span[n] 个开关，则 *所有 #cf_span[m] 个灯泡都会被点亮*。\n\n你认为开关太多了，希望忽略其中一个。\n\n你的任务是判断是否存在这样一个开关：若忽略它（不使用），但按下其余 #cf_span[n - 1] 个开关，所有 #cf_span[m] 个灯泡仍会被点亮。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 2000]），分别表示开关数量和灯泡数量。\n\n接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个字符。字符 #cf_span[ai, j] 为 '_1_' 表示第 #cf_span[i] 个开关控制第 #cf_span[j] 个灯泡，为 '_0_' 表示不控制。\n\n保证若按下所有 #cf_span[n] 个开关，则 *所有 #cf_span[m] 个灯泡都会被点亮*。\n\n如果存在一个开关，忽略它并按下其余 #cf_span[n - 1] 个开关后所有 #cf_span[m] 个灯泡仍能被点亮，则输出 \"_YES_\"；否则输出 \"_NO_\"。"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 2000]），分别表示开关数量和灯泡数量。接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个字符。字符 #cf_span[ai, j] 为 '_1_' 表示第 #cf_span[i] 个开关控制第 #cf_span[j] 个灯泡，为 '_0_' 表示不控制。保证若按下所有 #cf_span[n] 个开关，则 *所有 #cf_span[m] 个灯泡都会被点亮*。"},{"iden":"output","content":"如果存在一个开关，忽略它并按下其余 #cf_span[n - 1] 个开关后所有 #cf_span[m] 个灯泡仍能被点亮，则输出 \"_YES_\"；否则输出 \"_NO_\"。"},{"iden":"examples","content":"输入\n4 5\n10101\n01000\n00111\n10000\n输出\nYES\n\n输入\n4 5\n10100\n01000\n00110\n00101\n输出\nNO"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the number of switches, $ m $ the number of lamps, and $ A \\in \\{0,1\\}^{n \\times m} $ the incidence matrix where $ A_{i,j} = 1 $ if switch $ i $ controls lamp $ j $, and $ 0 $ otherwise.\n\nLet $ S_i \\subseteq \\{1, 2, \\dots, m\\} $ denote the set of lamps controlled by switch $ i $, i.e., $ S_i = \\{ j \\mid A_{i,j} = 1 \\} $.\n\nDefine the union of all switches:  \n$$\nU = \\bigcup_{i=1}^n S_i = \\{1, 2, \\dots, m\\}\n$$  \n(given: all lamps are turned on when all switches are pressed).\n\nFor each switch $ i $, define the union of all other switches:  \n$$\nU_{-i} = \\bigcup_{\\substack{j=1 \\\\ j \\ne i}}^n S_j\n$$\n\nWe are to determine:  \nDoes there exist an index $ i \\in \\{1, 2, \\dots, n\\} $ such that $ U_{-i} = \\{1, 2, \\dots, m\\} $?\n\nEquivalently:  \nIs there a switch $ i $ such that for every lamp $ j \\in \\{1, 2, \\dots, m\\} $, there exists at least one switch $ k \\ne i $ with $ A_{k,j} = 1 $?\n\nThat is, for each lamp $ j $, define the set of switches that control it:  \n$$\nT_j = \\{ i \\in \\{1, \\dots, n\\} \\mid A_{i,j} = 1 \\}\n$$\n\nThen the condition holds if and only if there exists an $ i $ such that for all $ j \\in \\{1, \\dots, m\\} $, $ |T_j| \\ge 2 $ or $ i \\notin T_j $.\n\nIn other words:  \nThere exists an $ i \\in \\{1, \\dots, n\\} $ such that for every $ j \\in \\{1, \\dots, m\\} $, if $ T_j = \\{i\\} $, then the condition fails. So we require:  \n$$\n\\forall j \\in \\{1, \\dots, m\\}, \\quad |T_j| \\ge 2 \\quad \\text{or} \\quad i \\notin T_j\n$$\n\nBut since we are to find *some* $ i $ such that removing it still covers all lamps, the condition is:  \n$$\n\\exists i \\in \\{1, \\dots, n\\} \\text{ such that } \\bigcup_{k \\ne i} S_k = \\{1, \\dots, m\\}\n$$\n\nWhich is equivalent to:  \n$$\n\\exists i \\in \\{1, \\dots, n\\} \\text{ such that } \\forall j \\in \\{1, \\dots, m\\}, \\quad T_j \\not\\subseteq \\{i\\}\n$$\n\nThat is, no lamp is **uniquely** controlled by switch $ i $ — but more precisely, for the chosen $ i $, **no lamp** has its *only* controlling switch being $ i $.\n\nThus, define for each lamp $ j $:  \n- If $ |T_j| = 1 $, then the unique switch in $ T_j $ is **critical** for lamp $ j $.\n\nLet $ C = \\{ i \\in \\{1, \\dots, n\\} \\mid \\exists j \\text{ such that } T_j = \\{i\\} \\} $ — the set of critical switches.\n\nThen:  \nThere exists a switch $ i $ to ignore such that all lamps remain on **if and only if** $ i \\notin C $.\n\nThat is, if $ C \\ne \\{1, \\dots, n\\} $, then any switch not in $ C $ can be ignored.\n\nBut note: It is guaranteed that $ \\bigcup_{i=1}^n S_i = \\{1, \\dots, m\\} $, so every lamp is covered.\n\nTherefore:\n\n> **Answer is \"YES\" if and only if there exists at least one switch $ i $ that is not the unique controller of any lamp.**  \n> Equivalently: **\"YES\" if and only if $ C \\ne \\{1, \\dots, n\\} $** — i.e., not every switch is critical for at least one lamp.\n\nFormally:\n\nLet $ \\text{critical}(i) = \\exists j \\in \\{1, \\dots, m\\} \\text{ such that } T_j = \\{i\\} $\n\nThen:  \n$$\n\\boxed{\n\\text{Answer} =\n\\begin{cases}\n\\text{YES} & \\text{if } \\exists i \\in \\{1,\\dots,n\\} \\text{ such that } \\neg \\text{critical}(i) \\\\\n\\text{NO} & \\text{otherwise}\n\\end{cases}\n}\n$$","simple_statement":null,"has_page_source":false}