Module: Cây bao trùm: Thuật toán Kruskal

Problem

Besi nằm trên một mạng gồm N (2≤N≤10⁵) đỉnh có nhãn 1…N và 2N cổng có nhãn 1…2N. Mỗi cổng kết nối hai đỉnh khác nhau u và v (u≠v). Một tập hợp các cổng có thể kết nối một số cặp đỉnh.
Mỗi đỉnh v liền kề với bốn cổng khác nhau. Danh sách các cổng của v được cho bởi pv=[p_v,1,p_v,2,p_v,3,p< sub>v ,4].

Vị trí hiện tại của bạn có thể được biểu thị bằng một cặp có thứ tự (đỉnh hiện tại, cổng hiện tại); tức là một cặp (v,p_v,i) trong đó 1≤v≤N và 1≤i≤4. Bạn có thể sử dụng một trong các thao tác sau để thay đổi vị trí hiện tại của mình:

Thay đổi đỉnh hiện tại bằng cách di chuyển qua cổng hiện tại.
Chuyển đổi cổng thông tin hiện tại. Tại mỗi đỉnh, hai cổng đầu tiên trong danh sách được ghép nối và hai cổng cuối cùng trong danh sách cũng được ghép nối. Vì vậy, nếu trạng thái hiện tại của bạn là (v,p_v,2), thì bạn có thể chuyển sang sử dụng cổng (v,p_v,1) và ngược lại. Tương tự, nếu vị trí hiện tại của bạn là (v,p_v,3), bạn có thể chuyển sang cổng (v,p_v,4) và quay lại. không được phép chuyển đổi khác (ví dụ: bạn không thể chuyển từ cổng pv,2 sang cổng) p_v,4).
Tổng cộng có 4N trạng thái khác nhau. Thật không may, có thể không phải là bất kỳ trạng thái nào cũng có thể đạt được từ bất kỳ trạng thái nào bằng một chuỗi các hoạt động đã cho. Do đó, với chi phí là cv (1≤c_v≤1000) mặt trăng, bạn có thể sắp xếp lại danh sách các cổng liền kề với v, theo bất kỳ thứ tự nào bạn muốn. Sau đó, hai cổng đầu tiên trong danh sách được kết hợp thành một cặp và hai cổng cuối cùng thành một cặp khác.

Ví dụ: nếu bạn sắp xếp lại các cổng của v theo thứ tự [p_v,3,p_v,1,p_v,2, p_v,4], Điều này có nghĩa là. nếu bạn ở trên v thì sao

Nếu đang ở trong cổng p_v,1, bạn có thể chuyển sang cổng p_v,3 và quay lại
Nếu đang ở trong cổng p_v,2, bạn có thể chuyển sang cổng p_v,4 và quay lại
Bây giờ bạn không thể chuyển từ cổng p_v,1 sang p_v,2 hoặc từ cổng p_v,3 sang cổng p _v,4 và ngược lại.
Tính toán số lượng mặt trăng tối thiểu cần thiết để sửa đổi mạng theo cách sao cho mỗi trạng thái có thể truy cập được từ mỗi trạng thái. Đảm bảo rằng dữ liệu thử nghiệm được xây dựng theo cách có ít nhất một cách để sửa đổi mạng theo cách này.

Đầu vào: 
Dòng đầu tiên chứa N.
Mỗi dòng trong số N dòng tiếp theo mô tả một đỉnh. Chuỗi v+1 chứa 5 số nguyên cách nhau bởi dấu cách c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
Đảm bảo rằng với mỗi v tất cả p_v,1,p_v,2,p_v,3,p_{v, 4} khác biệt và mỗi cổng xuất hiện trong danh sách có đúng hai đỉnh.

Đầu ra: 
Một dòng ghi số lượng mặt trăng tối thiểu cần thiết để sửa đổi mạng sao cho mỗi trạng thái có thể đến được từ một trạng thái khác.
 

Ví dụ

<đầu>

#	Đầu vào	Đầu ra	Giải thích
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Chỉ cần hoán đổi danh sách các đỉnh 1 và 4 là đủ. Điều này yêu cầu c1+c4=13 mun. Các hoán vị là: p1=[1,9,4,8] và p4=[7,4,6,3].