D - Placement of Security Guards Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、直線状に並んだ N 個の区画（区画 1 から区画 N まで）からなる長い廊下の警備計画を立てています。すべての区画に警備が行き届くようにしなければなりません。

高橋君は M 人の警備員候補を集めました。各警備員候補 i （ 1 \leq i \leq M ）は、区画 L_i から区画 R_i までの連続する範囲を担当することができます。つまり、警備員候補 i を配置すると、区画 L_i, L_i + 1, \ldots, R_i のすべてに警備が行き届きます。

高橋君は、 N 個すべての区画に警備が行き届くようにしたいと考えています。具体的には、 M 人の警備員候補の中から何人かを選び、選んだ警備員たちが担当する区画の集合の和集合が \{1, 2, \ldots, N\} と一致するようにしたいです。ただし、各警備員候補は選ぶか選ばないかの二択であり、同じ候補を複数回選ぶことはできません。

このとき、配置する警備員の人数の最小値を求めてください。ただし、どのように警備員を選んでもすべての区画に警備を行き届かせることが不可能な場合は、 -1 を出力してください。

制約

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 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 が、空白区切りで与えられる。
  • 2 行目から M + 1 行目では、各警備員候補が担当できる区画の範囲が与えられる。
  • i + 1 行目（ 1 \leq i \leq M ）では、警備員候補 i が担当できる区画の範囲の左端 L_i と右端 R_i が、空白区切りで与えられる。

出力

すべての区画に警備を行き届かせるために必要な警備員の最小人数を 1 行で出力してください。不可能な場合は -1 を出力してください。

入力例 1

10 3
1 5
3 7
6 10

出力例 1

2

入力例 2

15 4
1 3
5 8
10 12
13 15

出力例 2

-1

入力例 3

1000000000 5
1 300000000
200000000 500000000
400000000 700000000
600000000 900000000
800000000 1000000000

出力例 3

5

Score : 400 pts

Problem Statement

Takahashi is creating a security plan for a long corridor consisting of N sections (from section 1 to section N) arranged in a straight line. He must ensure that all sections are covered by security.

Takahashi has gathered M guard candidates. Each guard candidate i (1 \leq i \leq M) can cover a contiguous range from section L_i to section R_i. That is, if guard candidate i is assigned, sections L_i, L_i + 1, \ldots, R_i are all covered.

Takahashi wants all N sections to be covered. Specifically, he wants to select some of the M guard candidates such that the union of the sections covered by the selected guards equals \{1, 2, \ldots, N\}. Each guard candidate can either be selected or not selected; the same candidate cannot be selected more than once.

Find the minimum number of guards that need to be assigned. If it is impossible to cover all sections regardless of how the guards are selected, output -1.

Constraints

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • All inputs are integers

Input

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains an integer N representing the number of sections and an integer M representing the number of guard candidates, separated by a space.
  • From the 2nd line to the (M + 1)-th line, the range of sections each guard candidate can cover is given.
  • The (i + 1)-th line (1 \leq i \leq M) contains the left endpoint L_i and right endpoint R_i of the range of sections that guard candidate i can cover, separated by a space.

Output

Output in a single line the minimum number of guards needed to cover all sections. If it is impossible, output -1.

Sample Input 1

10 3
1 5
3 7
6 10

Sample Output 1

2

Sample Input 2

15 4
1 3
5 8
10 12
13 15

Sample Output 2

-1

Sample Input 3

1000000000 5
1 300000000
200000000 500000000
400000000 700000000
600000000 900000000
800000000 1000000000

Sample Output 3

5