Đèn màu

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,\dots ,n-1$), bóng $1$ xếp kế tiếp bóng thứ $n$;
• Giữa hai bóng bất kỳ $i,j$ ($i\ne 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\ne 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 dự 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,\dots ,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.

Các thao tác được thực hiện lần lượt, mỗi thao tác giữ nguyên kết quả đổi màu của các thao tác trước. Một cặp bóng có thể được bấm nhiều lần; bấm cặp $j,i$ cũng là đổi màu dây nối giữa hai bóng $i,j$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,m$;
• $m$ dòng sau, dòng thứ $k$ chứa hai số nguyên dương $i_k,j_k$ ($i_k\ne j_k$) cách nhau bởi dấu cách.

Dữ liệu ra

Gồm $m$ dòng, dòng thứ $k$ 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 thao tác thứ $k$.

Ràng buộc

• $2\le n\le {10}^5$; $1\le m\le {10}^5$.
• $1\le i_k,j_k\le n$, $i_k\ne j_k$.

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$.

Ví dụ