Bessie đang ở trong một mạng lưới gồm \(N\) đỉnh (\(2\le N\le10^5\)) được đánh số \(1\ldots N\) và \(2N\) cổng được đánh số \(1\ldots2N\). Mỗi cổng nối hai đỉnh phân biệt \(u\) và \(v\) (\(u\ne v\)). Nhiều cổng có thể nối cùng một cặp đỉnh.

Mỗi đỉnh \(v\) kề với bốn cổng phân biệt. Danh sách các cổng kề với \(v\) là \(p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]\).

Vị trí hiện tại của bạn được biểu diễn bằng cặp có thứ tự \((\text{\u0111ỉnh hiện tại},\text{cổng hiện tại})\), tức một cặp \((v,p_{v,i})\) với \(1\le v\le N\) và \(1\le i\le4\). Bạn có thể dùng một trong hai thao tác sau để thay đổi vị trí hiện tại:

1. Thay đổi đỉnh hiện tại bằng cách đi qua cổng hiện tại.
2. Chuyển cổng hiện tại. Tại mỗi đỉnh, hai cổng đầu tiên trong danh sách được ghép thành một cặp, và hai cổng cuối cũng cũng được ghép thành một cặp. Cụ thể, nếu vị trí hiện tại là \((v,p_{v,2})\) thì bạn có thể chuyển sang cổng \((v,p_{v,1})\) và ngược lại. Tương tự, bạn có thể chuyển qua lại giữa \((v,p_{v,3})\) và \((v,p_{v,4})\). Không được phép chuyển theo bất kỳ cách nào khác; chẳng hạn, không thể chuyển từ \(p_{v,2}\) sang \(p_{v,4}\).

Có tổng cộng \(4N\) vị trí phân biệt. Đáng tiếc là có thể không phải mọi vị trí đều đến được từ mọi vị trí khác bằng một chuỗi thao tác. Vì vậy, với chi phí \(c_v\) moonie (\(1\le c_v\le1000\)), bạn có thể hoán vị danh sách cổng kề với \(v\) theo bất kỳ thứ tự nào. Sau đó, hai cổng đầu tiên trong danh sách mới được ghép với nhau, và hai cổng cuối cũng cũng được ghép với nhau.

Ví dụ, nếu bạn hoán vị các cổng kề với \(v\) thành thứ tự \([p_{v,3},p_{v,1},p_{v,2},p_{v,4}]\), thì tại đỉnh \(v\):

• có thể chuyển qua lại giữa \(p_{v,1}\) và \(p_{v,3}\);
• có thể chuyển qua lại giữa \(p_{v,2}\) và \(p_{v,4}\);
• không còn có thể chuyển qua lại giữa \(p_{v,1}\) và \(p_{v,2}\), hay giữa \(p_{v,3}\) và \(p_{v,4}\).

Hãy tính tổng số moonie nhỏ nhất cần dùng để sửa đổi mạng sao cho có thể đến mọi vị trí từ mọi vị trí khác. Dữ liệu bảo đảm tồn tại ít nhất một cách sửa đổi mạng hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một đỉnh. Dòng \(v+1\) chứa năm 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}\).

Với mỗi \(v\), bốn giá trị \(p_{v,1},p_{v,2},p_{v,3},p_{v,4}\) đều phân biệt. Mỗi cổng xuất hiện trong danh sách kề của đúng hai đỉnh.

Dữ liệu ra

In trên một dòng tổng số moonie nhỏ nhất cần dùng để sửa đổi mạng sao cho có thể đến mọi vị trí từ mọi vị trí khác.

Phân nhóm

• Trong các test 2-4, \(c_v=1\) với mọi \(v\).
• Các test 5-12 không có ràng buộc bổ sung.

Ví dụ

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 vị danh sách kề của các đỉnh \(1\) và \(4\). Việc này tốn tổng cộng \(c_1+c_4=13\) moonie. Ta có thể đặt \(p_1=[1,9,4,8]\) và \(p_4=[7,4,6,3]\).

Nguồn

USACO 2021 US Open, Gold - Portals: https://usaco.org/index.php?page=viewproblem2&cpid=1138

Tác giả: Benjamin Qi.