#815. CONCOMP - Thành phần liên thông

Trường CHV có một hệ thống mạng máy tính, bao gồm máy tính và 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ừ đến , các dây cáp nối được đánh chỉ số từ đến . Thầy Cường, ngoài công việc giảng dạy cho học sinh đội tuyển Tin học còn được ban giám hiệu giao cho trọng trách quản trị hệ thống mạng. 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 môn Tin học, thầy Cường đư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 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ừ đến .
• Đế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ừ đến .

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 thầy Cường đưa ra, các em hãy cùng các bạn học sinh đội tuyển Tin học trường thực hiện thí nghiệm trên.

Dữ liệu vào:

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

Dữ liệu ra:

• Ghi ra 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.

Ví dụ:

Dữ liệu vào:

6 5
1 2
5 4
2 3
3 1
3 6
6
1 3
2 5
1 5
5 5
2 4
3 3

Dữ liệu ra:

4
5
6
3
4
2

Giới hạn:

• Có số test ứng với số điểm có ;
• Có số test khác ứng với số điểm có ;
• Có số test còn lại ứng với số điểm có .