Bức ảnh (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho dãy gồm $N$ vị trí được đánh số từ $1$ đến $N$ . Mỗi vị trí có thể được đánh dấu hoặc không. Bạn được cho $M$ đoạn, đoạn thứ $i$ bao gồm các vị trí từ $a_{i}$ đến $b_{i}$ (bao gồm cả hai đầu). Biết rằng mỗi đoạn chứa đúng một vị trí được đánh dấu.

Hãy tìm số lượng lớn nhất các vị trí có thể được đánh dấu sao cho thỏa mãn tất cả các ràng buộc trên. Nếu không tồn tại cách đánh dấu hợp lệ, in ra $- 1$ .

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ .
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}$ và $b_{i}$ mô tả một đoạn.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng lớn nhất các vị trí được đánh dấu, hoặc $- 1$ nếu không có cách đánh dấu hợp lệ.

Ràng buộc

$1 \leq N \leq 200 000$
$1 \leq M \leq 100 000$
$1 \leq a_{i} \leq b_{i} \leq N$

Ví dụ

Input	Output	Giải thích
5 3 1 4 2 5 3 4	1	Đoạn $[3, 4]$ phải chứa đúng một vị trí đánh dấu. Nếu đánh dấu vị trí $3$ , cả ba đoạn đều chứa đúng một vị trí đánh dấu. Không thể đánh dấu thêm vị trí nào mà vẫn đảm bảo mỗi đoạn chỉ chứa đúng một.
6 2 1 3 4 6	2	Hai đoạn $[1, 3]$ và $[4, 6]$ không giao nhau. Ta đánh dấu vị trí $2$ (phủ đoạn $[1, 3]$ ) và vị trí $5$ (phủ đoạn $[4, 6]$ ). Mỗi đoạn chứa đúng một vị trí đánh dấu, và đây là số lượng lớn nhất.

Ghi chú

Lưu ý rằng mỗi đoạn phải chứa đúng một vị trí đánh dấu, không phải ít nhất một.

Bình luận

Không có bình luận tại thời điểm này.