#1480 · Hệ thống mạng

Khu Thu Duc Compus trường HUTECH có trang bị hệ thống mạng máy tính Cisco, bao gồm N máy tính và M cáp kết nối một số cặp máy tính. Các máy tính được đánh chỉ số từ 1 đến N, các dây cáp nối được đánh chỉ số từ 1 đến M.

Trong bài giảng chuyên đề về thành phần liên thông trên đồ thị cho học sinh đội tuyển Olympic, thầy Khuyên đưa ra bài toán nhằm kiểm tra về độ tin cậy của mạng bằng một loạt các thí nghiệm trên mạng máy tính, mỗi thí nghiệm thực hiện 3 thao tác theo thứ tự sau:

• Tạm thời ngắt kết nối các dây cáp có chỉ số từ l đến r.
• Đếm số lượng các thành phần máy tính liên thông trong mạng được xác định tại thời điểm đó.
• Kết nối lại các dây cáp bị ngắt kết nối có chỉ số từ l đến r.

Quy ước: Một máy tính không kết nối với máy tính nào cũng được coi là một thành phần liên thông.

Yêu cầu: Với mỗi cặp chỉ số dây cáp l, r thầy Khuyên đưa ra, các bạn hãy cùng các đội tuyển Olympic trường HUTECH thực hiện thí nghiệm trên.

• Dòng đầu tiên chứa hai số nguyên N và M (2 \leq N \leq 10 ; 1 \leq M \leq 50)
• M dòng tiếp theo mỗi dòng chứa hai số nguyên u, v thể hiện máy tính u kết nối với máy tính v trong mạng.
• Dòng tiếp theo chứa số nguyên k (1 \leq k \leq 50) là số lượng thí nghiệm.
• k dòng tiếp theo, mỗi dòng chứa hai số nguyên l, r (1 \leq l \leq r \leq M) thể hiện một thí nghiệm trên mạng máy tính.

Ghi ra k dòng, mỗi dòng chỉ ra một số nguyên là số thành phần máy tính liên thông tương ứng với mỗi thí nghiệm.