LAMP - Đèn màu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: dahaodl

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ữ hai cặp bóng bất kỳ i, j (i ≠ 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 ≠ 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 ik, jk (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.

Dữ liệu:

- 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 ≠ j) cách nhau bởi dấu cách.

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.

Ràng buộc: n ≤ 10^5; m ≤ 10^5

Ví dụ

  • input
    4 3
    1 2
    2 3
    3 1
    output
    2
    1
    1
Back to Top