Ông Joe làm chủ một trang trại nuôi cừu. Một bữa nọ, để kiểm kê số lượng, Joe xếp N (1 <= N <= 200,000) con cừu của mình thành một hàng dài (trang trại của ông rất rộng lớn). Do đây là trang trại kiểu mẫu của quận nên được nhiều phóng viên đến chụp ảnh. Họ chụp được tổng cộng M (1 <= M <= 100,000) bức ảnh , bức ảnh thứ i ghi lại khoảnh khắc từ con cừu ở vị trí a_i đến vị trí b_i. Mỗi con cừu hiện diện trong ít nhất một bức ảnh.

Sau khi đưa tin, sở y tế phát hiện sự bất thường đến từ màu lông khác lạ của một số con cừu. Ông Joe được phóng viên cung cấp lại tất cả các bức ảnh đã chụp và ông cũng nhận thấy điều này. Thật trùng hợp rằng mỗi bức ảnh chứa chính xác một con cừu khác lạ.

Sở y tế đưa ra tối hậu thư rằng trong vòng một ngày, ông Joe phải báo cáo số lượng chính xác các con cừu khác lạ. Thời gian quá gấp rút, ông không thể kiểm đếm lại trực tiếp từ đàn cừu, thứ duy nhất ông có thể căn cứ là các bức ảnh được cung cấp. Bạn là một nhân viên thân thiết của Joe, hãy giúp ông tính toán số lượng tối đa các con cừu khác lạ có thể có.

Dữ liệu đầu vào:
- Dòng đầu tiên chứa 2 số nguyên N và M
- M dòng tiếp theo chứa các bộ số a_i và b_i mô tả bức ảnh thứ i

Dữ liệu đầu ra: số nguyên duy nhất ghi lại số lượng tối đa các con cừu khác lạ có thể có. Nếu không có kết quả nào phù hợp thì xuất ra -1.

Ví dụ: