题目描述

对于整数列 $X=(X_1,X_2,\dots,X_n)$，用 $X[L,R]$ 表示整数列 $(X_L,X_{L+1},\dots,X_{R})$。

给定整数 $N,M$ 和 $M$ 组整数 $(A_i,B_i,C_i,D_i)$。

请判断是否存在一个长度为 $N$ 的整数列 $X$，使得对于所有 $i=1,2,\dots,M$，都满足以下条件：

• $X[A_i,B_i]$ 在字典序上小于 $X[C_i,D_i]$。

数列的字典序定义如下：设数列 $S=(S_1,S_2,\ldots,S_{|S|})$，$T=(T_1,T_2,\ldots,T_{|T|})$，若满足以下 1. 或 2. 中的任意一个，则称 $S$ 在字典序上小于 $T$。其中 $|S|,|T|$ 分别表示 $S,T$ 的长度。

1. $|S|<|T|$ 且 $(S_1,S_2,\ldots,S_{|S|})=(T_1,T_2,\ldots,T_{|S|})$。
2. 存在整数 $1\leq i\leq \min\lbrace |S|,|T| \rbrace$，使得以下两点都成立：
   • $(S_1,S_2,\ldots,S_{i-1})=(T_1,T_2,\ldots,T_{i-1})$
   • $S_i$ 小于 $T_i$（作为数值比较）。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_M$ $B_M$ $C_M$ $D_M$

输出格式

如果存在满足条件的整数列，则输出 Yes，否则输出 No。

样例 1

输入

4 2
1 3 3 4
4 4 1 2

输出

Yes

样例 2

输入

3 2
1 2 2 3
2 2 1 1

输出

No

样例 3

输入

15 20
2 5 6 14
11 14 10 10
13 15 6 10
8 10 3 8
7 8 1 9
2 8 14 15
14 14 5 12
6 10 9 9
1 4 10 14
5 14 6 7
8 10 5 8
8 10 11 15
4 8 4 11
7 9 1 4
8 10 3 3
11 13 8 14
6 13 4 15
4 7 6 11
2 5 1 2
8 14 6 8

输出

No

说明/提示

数据范围

• $2\leq N\leq 2000$
• $1\leq M\leq 2000$
• $1\leq A_i\leq B_i\leq N$
• $1\leq C_i\leq D_i\leq N$
• 输入的所有值均为整数

样例解释 1

例如 $X=(1,1,2,1)$ 就满足所有条件。

样例解释 2

不存在满足条件的整数列 $X$。

由 ChatGPT 4.1 翻译