Farmer John muốn ghép ảnh toàn cảnh hàng $N$ bò ($(1 \le N \le 200,000)$), như thường lệ đánh số từ $1..N$. Ông chụp $M$ ảnh ($(1 \le M \le 100,000)$), mỗi ảnh phủ một đoạn liên tiếp: ảnh $i$ chứa bò $a_i$ đến $b_i$ kể cả hai đầu. Các ảnh gộp lại không nhất thiết chứa mọi bò.

FJ nhận ra mỗi ảnh có đúng một bò có đốm! Ông biết đàn có một số bò có đốm nhưng chưa từng đếm. Dựa vào ảnh, tìm số bò có đốm lớn nhất có thể trong đàn. Nếu không thể gán đốm cho bò phù hợp với mọi ảnh, in $-1$.

Dữ liệu vào

• Dòng $1$: hai số nguyên $N$ và $M$.

• Các dòng $2..M+1$: dòng $i+1$ chứa $a_i$ và $b_i$.

Dữ liệu ra

• Dòng $1$: số bò có đốm lớn nhất có thể, hoặc $-1$ nếu vô nghiệm.

Ví dụ

Dữ liệu vào 1

5 3
1 4
2 5
3 4

Dữ liệu ra 1

1

Ghi chú

Có $5$ bò và $3$ ảnh. Ảnh đầu chứa bò $1$ đến $4$, v.v.

Ảnh cuối cho biết bò $3$ hoặc $4$ phải có đốm. Chọn bất kỳ con nào trong hai con cũng thỏa hai ảnh đầu.

Tác giả bài toán: Brian Dean, 2013