问题 CW: 孙悟空和哪吒

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:257 通过:60

题目描述

   由于巨人头颅已经出现在天空中,所有人类都处于危险之中,所以来自所各星球的孙悟空和哪吒(英雄的代表)都聚集在一起,寻找解决方案。
有n个星球参与这个事件,也就是说,n个星球中的每一个星球都有一个孙悟空和一个哪吒参与。他们聚集在m组中。每个人都可以在多个组中,一个组可以包含任意数量的成员。

    来自地球的孙悟空知道在每个星球(包括地球)中,来自该星球的孙悟空和哪吒中有一个是叛徒,另一个是忠诚的,但没有人知道哪一个叛徒。他知道,如果有一个团体的每个成员都是叛徒(他们会计划和毁灭世界),那么拯救活动就注定要失败。

    地球的孙悟空知道,如果有一个小组存在所有成员都是叛徒的可能,他应该立即取消这个活动。所以他想知道他是否应该取消活动。你必须告诉他是的,当且仅当至少有一个团队可能出现所有成员都是叛徒的可能,这样在这种情况下世界就会结束。

输入格式

输入的第一行包含两个整数 n 和 m  (1≤n,m≤104) − 分别是星球数和组数。
接下来的 m 行包含有关组的信息。其中第 i 个首先包含一个整数 k,后跟 k 个整数 vi,1,vi,2,...,vi,k.如果vi,j为负数,则表示来自星球编号 vi,的孙悟空加入了这个组,否则意味着来自星球编号vi,的哪吒加入了这组。
所有组的 k 之和不超过104

输出格式

在一行中打印出问题的答案。如果应该取消活动,请打印“是”,否则打印“否”。
Examples
Input
4 2
1 -3
4 -2 3 2 -3
Output
YES
Input
5 2
5 3 -2 1 -1 5
3 -5 2 5
Output
NO
Input
7 2
3 -1 6 7
7 -5 4 2 -4 7 -3 6
Output
YES
Note
在第一个测试用例中,第一组只包含来自星球 3 的孙悟空,所以万一他是叛徒,那么这个组的所有成员都是叛徒,所以应该取消活动。


输入样例 复制

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

输出样例 复制

YES