Một số trường học được kết nối trong một mạng máy tính. Giữa các trường tồn tại các thỏa thuận hỗ trợ phần mềm. Mỗi trường đều có danh sách các trường mà nó phải hỗ trợ (trường hỗ trợ trường không có nghĩa là trường nhất định phải hỗ trợ trường ). Khi một trường nhận được một phần mềm mới, dù là nhận trực tiếp hay qua mạng, trường đó phải ngay lập tức chuyển phần mềm này qua mạng cho các trường mà nó hỗ trợ. Do đó, để một phần mềm mới được tất cả các trường trong mạng sử dụng, chỉ cần cung cấp nó cho một số trường nhất định.
Nhiệm vụ:
Hãy viết chương trình tính toán số lượng trường ít nhất cần được cung cấp trực tiếp phần mềm mới để phần mềm đó có thể truyền đến tất cả các trường thông qua mạng lưới hỗ trợ.
Nếu cho phép thêm các mối quan hệ hỗ trợ mới vào thỏa thuận hiện có, ta luôn có thể tạo ra một giao thức mới sao cho chỉ cần cung cấp phần mềm cho bất kỳ một trường nào, tất cả các trường khác đều có thể nhận được. Hãy tính số lượng mối quan hệ hỗ trợ mới ít nhất cần thêm vào để đạt được điều này.
Dữ liệu:
Dòng đầu tiên là một số nguyên dương , biểu thị tổng số trường kết nối mạng.
dòng tiếp theo biểu thị danh sách các trường mà mỗi trường cần hỗ trợ: dòng thứ liệt kê các mã số trường mà trường hỗ trợ, kết thúc bằng số .
Nếu một trường không hỗ trợ trường nào khác, dòng tương ứng sẽ chỉ có số . Nếu có nhiều số trên một dòng, chúng được phân cách bởi dấu cách.
Kết quả:
Gồm hai dòng.
Dòng đầu tiên là một số nguyên dương, biểu thị kết quả của nhiệm vụ 1.
Dòng thứ hai là một số nguyên dương, biểu thị kết quả của nhiệm vụ 2.
