Trần Đặng Tuấn Anh là một cựu học sinh xuất sắc của trường chuyên Lương Văn Tụy. Ngay từ những năm tháng học tại trường, Tuấn Anh đã có nhiều sản phẩm độc đáo, trí tuệ. Một trong các sản phẩm đó là chiếc đèn màu có hình dạng và nguyên tắc hoạt động như sau:

• Chiếc đèn có dạng là một hình tròn, trên viền có ~n~ bóng đèn, các bóng được đánh số từ 1 đến ~n~, xếp cách đều nhau theo chiều kim đồng hồ, bóng ~(i+1)~ xếp kế tiếp bóng ~i~ (~i = 1, 2, ..., n-1~), bóng 1 xếp kế tiếp bóng thứ ~n~;
• Giữa hai cặp bóng bất kỳ ~i, j~ (~i \neq j~) có một dây nối, dây nối này có thể sáng màu xanh hoặc sáng màu đỏ. Ban đầu tất cả các dây nối đều sáng màu xanh, nếu bấm đồng thời vào cặp bóng ~i, j~ (~i \neq j~) thì dây nối giữa hai bóng ~i, j~ sẽ đổi màu (đang là màu xanh đổi thành màu đỏ còn nếu là màu đỏ đổi thành màu xanh), đồng thời ở tâm chiếc đèn sẽ hiển thị số lượng tam giác mà có 3 đỉnh là 3 bóng trong ~n~ bóng, các dây nối giữa 3 bóng này sáng cùng màu.

Lấy ý tưởng từ chiếc đèn màu của Tuấn Anh, Ban giám khảo hội thi Duyên hải 2017, yêu cầu các thí sinh tham gia môn Tin học lập trình bài toán sau: Cho ~n~ là số bóng trên viền chiếc đèn và ~m~ thao tác bấm cặp bóng đèn ~i_k, j_k~ (~k = 1, 2, ..., m~), với mỗi thao tác hãy cho biết số lượng tam giác mà có 3 đỉnh là 3 bóng trong ~n~ bóng, các dây nối giữa 3 bóng này sáng cùng màu.

Input

• Dòng đầu chứa hai số nguyên ~n, m~;
• ~m~ dòng sau, mỗi dòng chứa hai số nguyên dương ~i, j~ (~i \neq j~) cách nhau bởi dấu cách.

Output

• Ghi ra kết quả gồm ~m~ dòng, mỗi dòng là số lượng tam giác mà có 3 đỉnh là 3 bóng trong ~n~ bóng, các dây nối giữa 3 bóng này sáng cùng màu sau mỗi thao tác.

Sample Input 1

4 3
1 2
2 3
3 1

Sample Output 1

2
1
1

Subtasks

• Có 25% số test ứng với 25% số điểm của bài có ~n \le 10^2; m \le 10^2~;
• Có 25% số test ứng với 25% số điểm của bài có ~n \le 10^2; m \le 10^5~;
• Có 25% số test khác ứng với 25% số điểm của bài có ~n \le 10^5; m \le 10^2~;
• Có 25% số test khác ứng với 25% số điểm còn lại của bài có ~n \le 10^5; m \le 10^5~.