Trong buổi sinh hoạt đầu năm, cô giáo chủ nhiệm giao cho Công Đức chụp lại một số tấm ảnh kỷ niệm cho lớp ITK19. Công Đức yêu cầu tất cả \(N\) bạn học sinh trong lớp (không tính cậu ấy) xếp thành một hàng và đánh số các bạn từ \(1\) đến \(N\) từ đầu hàng đến cuối hàng. Sau đó, cậu ấy chụp tổng cộng \(M\) tấm ảnh, tấm ảnh thứ \(i\) ghi lại hình ảnh một đoạn con từ học sinh \(a_i\) đến học sinh \(b_i\).

Sau khi quan sát \(M\) tấm ảnh được chụp, cô giáo nhận ra một hiện tượng: trong mỗi tấm ảnh có đúng một học sinh không mặc đồng phục! Vì số ảnh quá lớn nên cô rất ngại rà soát ngược lại từng tấm để điểm tên những học sinh này. Cô liền nhờ Đức lập trình xác định số lượng tối đa các bạn học sinh trong lớp không mặc đồng phục (không tính Đức) theo ràng buộc trên. Các bạn hãy giúp Đức nhé!

Input

Dòng đầu chứa hai số nguyên dương \(N\) và \(M\) (\(1\leq N\leq 2\cdot 10^5\), \(1\leq M\leq 10^5\)).

Dòng thứ \(i\) trong \(M\) dòng sau chứa hai số nguyên dương \(a_i\) và \(b_i\).

Ouput

Một số nguyên là số lượng lớn nhất có thể các học sinh không mặc đồng phục. Nếu không tìm được nghiệm thoả mãn thì in ra \(-1\).

Ví dụ

Sample input

5 3
1 4
2 5
3 4

Sample output

1

Giải thích

Từ tấm ảnh sau cùng, ta suy ra một trong hai học sinh: học sinh thứ \(3\) hoặc học sinh thứ \(4\), đang không mặc đồng phục. Chọn bất cứ học sinh nào trong số hai học sinh này cũng đều thỏa mãn ràng buộc cho hai tấm ảnh đầu.