D - 駐車場の割り当て 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君はショッピングモールの駐車場管理システムを開発しています。この駐車場には N 台分の駐車スペースが一列に並んでおり、入口側から順にスペース 1 、スペース 2 、...、スペース N と番号が付けられています。

今日は M 台の車が来場する予定があり、これらの車はすべて同じ時間帯に駐車場を利用します。 i 番目の車（ 1 \leq i \leq M ）は、スペース L_i からスペース R_i までの連続する駐車スペースのうち、いずれか 1 つに駐車することができます。

各車にはちょうど 1 つの駐車スペースを割り当てなければならず、同じ駐車スペースに 2 台以上の車を割り当てることはできません。

すべての車に駐車スペースを割り当てることが可能であれば Yes を、不可能であれば No を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq L_i \leq R_i \leq N （ 1 \leq i \leq M ）
  • 入力はすべて整数である

入力

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、駐車スペースの数 N と来場する車の台数 M が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目には、 i 番目の車が駐車可能なスペースの範囲を表す L_i と R_i が、スペース区切りで与えられる。

出力

すべての車に駐車スペースを割り当てることが可能であれば Yes を、不可能であれば No を 1 行で出力せよ。

入力例 1

5 3
1 2
2 3
1 3

出力例 1

Yes

入力例 2

4 5
1 2
1 2
3 4
3 4
2 3

出力例 2

No

入力例 3

10 7
1 5
2 6
3 7
1 3
5 8
7 10
8 10

出力例 3

Yes

Score : 400 pts

Problem Statement

Takahashi is developing a parking lot management system for a shopping mall. The parking lot has N parking spaces arranged in a row, numbered Space 1, Space 2, ..., Space N from the entrance side.

Today, M cars are scheduled to visit, and all of these cars will use the parking lot during the same time period. The i-th car (1 \leq i \leq M) can park in any one of the consecutive parking spaces from Space L_i to Space R_i.

Each car must be assigned exactly one parking space, and no parking space can be assigned to two or more cars.

If it is possible to assign a parking space to every car, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • All input values are integers

Input

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains the number of parking spaces N and the number of arriving cars M, separated by a space.
  • The i-th of the following M lines contains L_i and R_i, representing the range of spaces where the i-th car can park, separated by a space.

Output

Print Yes on a single line if it is possible to assign a parking space to every car, or No if it is not possible.

Sample Input 1

5 3
1 2
2 3
1 3

Sample Output 1

Yes

Sample Input 2

4 5
1 2
1 2
3 4
3 4
2 3

Sample Output 2

No

Sample Input 3

10 7
1 5
2 6
3 7
1 3
5 8
7 10
8 10

Sample Output 3

Yes