题目描述

有 $n$ 对夫妻被邀请参加一个 Party。因为场地的问题，每对夫妻只允许 一个人 参加（要么是丈夫，要么是妻子）。

在 $2n$ 个人之中，存在 $m$ 对 互相讨厌 的关系（讨厌关系都是两个人之间的）。

为了 Party 的和谐，互相讨厌的两人不能同时出席。给定全部互相讨厌的关系，请问能否在每对夫妻都派出 一个人 的前提下，让所有出席者都能愉快地相处？

输入格式

输入包含多组测试数据，每组数据格式如下：

第一行两个整数 $n$ 和 $m$，分别表示夫妻的对数和互相讨厌的关系对数。

接下来 $m$ 行，每行四个整数 $a_1, a_2, c_1, c_2$，表示第 $a_1$ 对夫妻的 $c_1$（$0$ 表示丈夫，$1$ 表示妻子）和第 $a_2$ 对夫妻的 $c_2$（$0$ 表示丈夫，$1$ 表示妻子）互相讨厌。

夫妻编号从 $0$ 开始（$0 \le a_1, a_2 < n$）。

输出格式

如果存在一种安排方案，使所有夫妻都能各派一人出席，输出 YES；否则输出 NO。

输入示例 1

2 1
0 1 1 1

输出示例 1

YES

示例 1 说明

有 $2$ 对夫妻和 $1$ 对讨厌关系：第 $0$ 对的妻子与第 $1$ 对的妻子互相讨厌。

可以让第 $0$ 对派丈夫、第 $1$ 对派妻子（或者反过来）出席，没有冲突，所以输出 YES。

输入示例 2

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

输出示例 2

NO

示例 2 说明

四条讨厌关系覆盖了第 $0$ 对与第 $1$ 对之间的 所有 $4$ 种派人组合：

• $(0 \text{ 派丈}, 1 \text{ 派丈})$ — 被关系 $1$ 禁止；
• $(0 \text{ 派丈}, 1 \text{ 派妻})$ — 被关系 $2$ 禁止；
• $(0 \text{ 派妻}, 1 \text{ 派丈})$ — 被关系 $3$ 禁止；
• $(0 \text{ 派妻}, 1 \text{ 派妻})$ — 被关系 $4$ 禁止。

所以两对夫妻无论如何安排都会冲突，输出 NO。

约束条件

• $1 \le n \le 1000$
• $1 \le m \le 10^6$
• $0 \le a_1, a_2 < n$，$a_1 \ne a_2$
• $c_1, c_2 \in \{0, 1\}$
• 所有输入值均为整数