{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Ở quốc gia Graphland, có nhiều thành phố nhưng không có đường sá. Chính phủ liên bang muốn thay đổi tình hình này và có kế hoạch xây dựng đường bộ và đường sắt sao cho tất cả các thành phố trong quốc gia được kết nối thông qua hệ thống giao thông mới này. Để làm cho hệ thống mới hiệu quả hơn, Graphland sẽ chỉ xây dựng đường bộ giữa các thành phố trong cùng một bang và sẽ sử dụng đường sắt để kết nối các thành phố ở các bang khác nhau. Để mục đích của bài toán này, xem xét rằng nếu khoảng cách giữa bất kỳ hai thành phố nào là tối đa r thì chúng thuộc cùng một bang. Để giảm thiểu chi phí xây dựng đường bộ và đường sắt, chính phủ cũng muốn chỉ xây dựng số lượng tối thiểu cần thiết của đường bộ và đường sắt sao cho có một lộ trình giữa bất kỳ cặp thành phố nào trong toàn quốc. Bạn đã được thuê để xác định hệ thống mạng lưới giao thông tối ưu mà Graphland phải xây dựng.\n\nDòng đầu tiên của đầu vào chứa số lượng trường hợp kiểm tra theo sau. Trên dòng đầu tiên của mỗi trường hợp kiểm tra, sẽ có hai số nguyên, n (1 \u003c n \u003c 1000), số lượng thành phố tạo nên Graphland, và r (0 \u003c r \u003c 40000), giá trị ngưỡng để xác định nếu hai thành phố ở trong cùng một bang. Trên các dòng tiếp theo, sẽ có một danh sách các tọa độ nguyên x - y (-10000 \u003c x,y \u003c 10000) trong kế hoạch cho mỗi thành phố ở Graphland. Chương trình của bạn phải xuất ra số lượng bang ở Graphland và số lượng tối thiểu cần mở rộng (làm tròn đến số nguyên gần nhất) của cả đường bộ và đường sắt phải được xây dựng để đáp ứng điều kiện của dự án.\n\n### Đầu vào\nDòng đầu tiên của đầu vào cho số lượng trường hợp, T (1 \u003c T \u003c 20). T trường hợp kiểm tra theo sau. Trên dòng đầu tiên của mỗi trường hợp kiểm tra, sẽ có hai số nguyên, n (1 \u003c n \u003c 1000), số lượng thành phố tạo nên Graphland, và r (0 \u003c r \u003c 40000), giá trị ngưỡng để xác định nếu hai thành phố ở trong cùng một bang. Trên các dòng tiếp theo, sẽ có một danh sách các tọa độ nguyên x - y (-10000 \u003c x,y \u003c 10000) trong kế hoạch cho mỗi thành phố ở Graphland.\n\n### Đầu ra\nĐầu ra bao gồm một dòng cho mỗi bộ dữ liệu đầu vào. Dòng này xác định bộ dữ liệu bằng một số (bắt đầu từ một và tăng lên ở mỗi bộ dữ liệu mới), theo sau là số lượng bang ở Graphland và số lượng tối thiểu cần mở rộng (làm tròn đến số nguyên gần nhất) của cả đường bộ và đường sắt phải được xây dựng để đáp ứng điều kiện của dự án.\n\nLưu ý: Lưu ý rằng, theo định nghĩa, nếu A và B ở trong cùng một bang, và B và C ở trong cùng một bang, thì A và C cũng ở trong cùng một bang.\n\n### Ví dụ \n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 100\n0 0\n1 0\n2 0\n3 1\n0 0\n100 0\n200 0\n4 20\n0 0\n40 30\n30 30\n10 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1 2 0\nCase #2: 3 0 200\nCase #3: 2 24 28\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}