← 返回题目列表

Codeforces · 1598/B

B. 组

中文机器翻译题面 查看原题

$$$n$$$ 学生参加了 Berland SU 编程课程的第一次会议($$$n$$$ 为偶数)。所有学生将被分为两组。每个小组每周将在五个工作日(星期一、星期二、星期三、星期四和星期五)之一参加一节课,并且为各小组选择的日期必须不同。此外,两个组应包含相同数量的学生。

每个学生都填写了一份调查,其中他们告诉自己一周中哪几天方便上课,哪几天不方便。

你的任务是确定是否可以选择两个不同的工作日来为小组安排课程(第一组将在第一个选定的日期上课,第二组将在第二个选定的日期上课),并将学生分成两组,使小组的人数相等,并且对于每个学生来说,为他们的小组选择的上课日期是方便的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1\,000$$$) — 学生人数。

接下来的$$$n$$$行的第$$$i$$$包含$$$5$$$个整数,每个整数是$$$0$$$或$$$1$$$。如果第 $$$j$$$ 个整数为 $$$1$$$,则第 $$$i$$$ 个学生可以在一周的第 $$$j$$$ 天参加课程。如果第 $$$j$$$ 个整数为 $$$0$$$,则第 $$$i$$$ 个学生无法参加一周中第 $$$j$$$ 的课程。

输入的附加限制:对于每个学生,一周中至少有一天是方便的,所有测试用例的学生总数不超过 $$$10^5$$$。

输出

对于每个测试用例打印一个答案。如果可以将学生分成人数相等的两组,并为各组选择不同的日期,以便每个学生都可以在其组的选定日期参加课程,请打印“是”(不带引号)。否则,打印“NO”(不带引号)。

示例

输入 #1

2
4
1 0 0 1 0
0 1 0 0 1
0 0 0 1 0
0 1 0 1 0
2
0 0 0 1 0
0 0 0 1 0

输出 #1

YES
NO

注意

在第一个测试用例中,有一种方法可以满足所有约束。例如,第一组可以由第一名和第三名学生组成,他们将在周四(第四天)上课;第二组可以由第二个和第四个学生组成,他们将在周二(第二天)上课。

在第二个测试用例中,不可能将学生分组,因此他们在不同的日子上课。