Nhân dịp đầu năm mới, CLB Môi Trường NBK quyết định tổ chức dọn rác ở bãi biển Tam Tiến cùng các bạn TNV của chương trình Clean up Việt Nam lần thứ 4. Là một người yêu thích công việc tình nguyện, thầy Phước dự định sẽ tham gia vào hoạt động lần này. Đồng thời thầy cũng muốn truyền ngọn lửa nhiệt huyết này đến các em học sinh lớp 10, nên đã quyết định rủ một số bạn học sinh ITK21 cùng tham gia.

Để có được một buổi sinh hoạt vui, khỏe, có ích, thầy phải chọn ra các bạn học sinh đoàn kết với nhau. Nhưng tiếc thay, sau các buổi board game chia cắt tình bạn của thầy Phước, một số bạn học sinh đã giận nhau và không muốn tham gia cùng nhau.

Lớp ITK21 gồm \(n\) học sinh được đánh số theo thứ tự từ \(1\) đến \(n\) trong danh sách lớp. Thầy muốn chọn ra một dãy các học sinh có số thứ tự liên tiếp nhau \(a,\ a+1,\ a+2,\ldots,\ b\ (a\leq b)\) sao cho trong đó không có hai bạn nào đang giận nhau để tham gia hoạt động.

Yêu cầu: Tính xem thầy có tất cả bao nhiêu cách chọn thỏa mãn yêu cầu.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) \((1\leq n\leq10^6, 1\leq m\leq10^5)\) - lần lượt là số học sinh của ITK21 và số cặp bạn đang giận nhau;
• Tiếp theo là \(m\) dòng, mỗi dòng gồm hai số nguyên dương \(x\) và \(y\) \((1\leq x,\ y\leq n, x\neq y)\) thể hiện hai học sinh \(x\), \(y\) đang giận nhau. Lưu ý các cặp có thể lặp lại.

Output

• Gồm một số nguyên duy nhất là số cách chọn thỏa mãn yêu cầu.

Ví dụ

Sample input 1

3 1
1 3

Sample output 1

5

Sample input 2

3 2
1 2
2 3

Sample output 2

3

Ràng buộc

• Có \(30\%\) test tương ứng với \(30\%\) số điểm có \(n\leq200\). Các test còn lại không có ràng buộc gì thêm.