Bức ảnh (Gold)

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\le N\le 200000$
• $1\le M\le 100000$
• $1\le a_i\le b_i\le N$

Ví dụ

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.