NGUỒN: Bài tập Bồi dưỡng HSGQG, Hải Phòng, T11/2020, Thái BK
Hệ thống mạng trên hành tinh XYZ thỏa mãn tính chất sau: Giữa hai đỉnh bất kỳ, tồn tại và duy nhất một đường đi đơn giữa chúng và được ký hiệu là . Nói cách khác, hệ thống mạng có dạng hình cây. Có một số cặp nút mạng đang truyền thông tin cho nhau, gọi là các kết nối. Với là một kết nối, ký hiệu và lần lượt là đỉnh gửi và đỉnh nhận .
Do tính chất của mạng quang không lọc, thông tin được gửi đi từ một nút nào đó sẽ lan truyền khắp nơi. Các đỉnh nhận sẽ phân biệt gói tin dựa vào chiều truyền đến của gói tin và bước sóng của kết nối. Ta nói kết nối làm nhiễu kết nối nếu tin từ và từ đến theo cùng một chiều, cụ thể là và có cạnh chung.
Trên thực tế, việc gán bước sóng cho các kết nối sẽ đưa về bài toán tô màu trên đồ thị quan hệ "làm nhiễu" nói trên. Tuy nhiên trong bài này, bạn chỉ cần tính số cung của đồ thị quan hệ đó, tức là số cặp mà làm nhiễu .
Các kết nối trên mạng có tính trực tuyến. Ban đầu chưa có kết nối nào, sau đó có thể có thêm các kết nối hoặc một số kết nối mất đi. Sau mỗi lần biến đổi như vậy, hãy tính toán và đưa ra số cặp mà làm nhiễu .
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương là số đỉnh của cây và số thay đổi của mạng;
dòng tiếp theo mỗi dòng ghi một cạnh của cây ;
dòng tiếp theo mỗi dòng ghi một biến đổi của mạng với là đỉnh gửi, là đỉnh nhận, tương ứng là có thêm hoặc mất đi một kết nối từ đến .
Dữ liệu đảm bảo có ít nhất một kết nối từ đến khi , và nếu có nhiều kết nối từ đến thì mỗi lần chỉ mất đi một trong số đó. Các đỉnh của cây được đánh số từ .
