\(N\) cô bò của Farmer John (\(4 \le N \le 12\), \(N\) chẵn) đã xây dựng một hệ thống thô sơ để các cặp bò thân thiết liên lạc với nhau bằng những sợi dây được bảo vệ bởi lớp bọc làm từ cỏ khô.

Mỗi cô bò có đúng 3 người bạn khác trong chuồng, và các cô bò phải tự sắp xếp để đứng trong \(N\) ô chuồng thẳng hàng. Một sợi dây có độ dài \(L\) cần đúng \(L\) đơn vị cỏ khô để làm, vì vậy, chẳng hạn nếu hai cô bò trong ô chuồng 4 và 7 là bạn thì cần 3 đơn vị cỏ khô để làm một sợi dây nối chúng.

Giả sử mỗi cặp bò thân thiết phải được nối bằng một sợi dây riêng, hãy xác định lượng cỏ khô ít nhất có thể cần để làm các sợi dây nếu các cô bò tự sắp xếp theo thứ tự tối ưu.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\). Các cô bò của FJ được đánh số thuận tiện từ 1 đến \(N\).
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách và nằm trong khoảng từ 1 đến \(N\). Dòng \(i+1\) chứa số hiệu của ba người bạn của cô bò \(i\). Nếu cô bò \(i\) là bạn của cô bò \(j\), thì cô bò \(j\) cũng là bạn của cô bò \(i\).

Dữ liệu ra

• Dòng 1 chứa tổng lượng cỏ khô ít nhất cần để nối tất cả các cặp bò thân thiết.

Ví dụ

6
6 2 5
1 3 4
4 2 6
5 3 2
4 6 1
1 5 3

17

Nguồn

USACO 2013 US Open, Bronze — Problem 4: Haywire

Tác giả đề: Brian Dean, 2013.