Cây khung nhỏ nhất bằng thuật toán Kruskal và DSU

Mục tiêu kiến thức

• Cài đặt cấu trúc dữ liệu Các tập hợp rời rạc (Disjoint Set Union - DSU) với kỹ thuật Nén đường đi (Path Compression) và Gộp theo hạng/kích thước (Union by Rank/Size) đạt độ phức tạp gần như hằng số O(α(N)).
• Cài đặt thuật toán Kruskal tìm Cây khung nhỏ nhất (Minimum Spanning Tree - MST) trong O(E log E).
• Kiểm tra tính liên thông toàn bộ của đồ thị sau khi dựng cây khung.
• Quản lý tổng chi phí lớn bằng kiểu long long.

Mô tả bài toán

AI Empire Academy cần lắp đặt hệ thống cáp mạng quang tốc độ cao kết nối N trạm nghiên cứu trí tuệ nhân tạo (1 ≤ N ≤ 10⁵). Có M tuyến cáp tiềm năng hai chiều có thể lắp đặt (0 ≤ M ≤ 2 · 10⁵). Tuyến cáp thứ i nối giữa trạm u và trạm v có chi phí lắp đặt là W (1 ≤ W ≤ 10⁹).

Mục tiêu là chọn ra một tập hợp các tuyến cáp sao cho:

• Tất cả N trạm nghiên cứu đều liên thông được với nhau (từ một trạm bất kỳ có thể truyền dữ liệu tới bất kỳ trạm nào khác).
• Tổng chi phí lắp đặt là nhỏ nhất có thể.

Bạn hãy viết chương trình:

• Nếu đồ thị liên thông và lắp đặt được: In ra tổng chi phí nhỏ nhất của cây khung.
• Nếu đồ thị không thể liên thông hoàn toàn (không thể kết nối đủ N trạm): In ra -1.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 10⁵.
• 0 ≤ M ≤ 2 · 10⁵.
• 1 ≤ W ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.