← 返回题目列表

Codeforces · 787/B

B. 不害怕

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

自从巨大的头颅出现在天空中以来,所有人类都处于危险之中,因此来自所有平行宇宙的所有瑞克和莫蒂都聚集在一起,寻找摆脱它们的解决方案。

有 n 个平行宇宙参与此活动(n 个瑞克和 n 个莫蒂)。 IE。 n 个宇宙中的每一个都有一个瑞克和一个莫蒂。他们聚集成 m 组。每个人可以属于多个组,并且一个组可以包含任意数量的成员。

Ricks and Mortys 已在这些群组中在线注册。因此,一个人可以多次加入一个群组(该网站的开发者没有考虑这种可能性)。

来自第 1 宇宙的夏天知道,在每个平行宇宙(包括她的宇宙)中,来自该宇宙的瑞克和莫蒂中只有一个是叛徒并且是忠诚的,但没有人知道是哪一个。她知道,如果有一个团体,该团体中的每个成员都是叛徒(他们将计划并毁灭世界),那么我们就注定要失败。

Summer知道,如果世界有可能终结(有一个组织,所有成员都是叛徒),她应该立即取消这个活动。所以她想知道是否应该取消这次活动。当且仅当存在至少一种情况(在所有 2n 种可能的情况中,每个宇宙中谁是叛徒有 2 种可能的情况)时,你必须告诉她“是”,这样在这种情况下世界将会终结。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 104) — 分别是宇宙数和组数。

接下来的 m 行包含有关组的信息。其中第 i 个首先包含一个整数 k(某人加入第 i 个组的次数,k > 0),后跟 k 个整数 vi, 1, vi, 2, ..., vi, k。如果vi,j为负数,则表示宇宙号-vi,j的Rick加入了该组,否则表示宇宙号vi,j的Morty加入了该组。

所有组的 k 总和不超过 104。

输出

在一行中打印 Summer 问题的答案。如果她应该取消活动,则打印“是”,否则打印“否”。

示例

输入 #1

4 2
1 -3
4 -2 3 2 -3

输出 #1

YES

输入 #2

5 2
5 3 -2 1 -1 5
3 -5 2 5

输出 #2

NO

输入 #3

7 2
3 -1 6 7
7 -5 4 2 4 7 -3 4

输出 #3

YES

注意

在第一个示例测试用例中,第一组仅包含来自第 3 号宇宙的 Rick,因此如果他是叛徒,那么该组的所有成员都是叛徒,因此 Summer 应该取消该活动。