#1151. PATROL2 - Tuần tra

Khu đô thị mới có tiểu khu đánh số từ đến . Có đường nối các tiểu khu, mỗi đường nối hai tiểu khu khác nhau. Từ một tiểu khu có thể tới tiểu khu khác (trực tiếp hoặc qua các tiểu khu trung gian). Độ dài của mỗi đường xấp xỉ như nhau và coi là bằng . Để đảm bảo an ninh hàng ngày cảnh sát phải đi tuần tra trên tất cả các đường trong khu đô thị, xuất phát từ trụ sở ở tiểu khu và cuối ngày trở về trụ sở. Như vậy mỗi con đường phải đi qua hai lần.

Ví dụ, với , độ dài đường đi tuần tra mỗi ngày là .

Để giảm độ dài đường tuần tra mà vẫn đảm bảo cảnh sát ngày nào cũng có mặt ở mỗi tiểu khu ít nhất một lần, chính quyền quyết định mở thêm đường tắt , mỗi đường tắt nối hai tiểu khu hoặc nối một tiểu khu với chính nó. Tránh dư luận cho rằng chính quyền ném tiền qua cửa sổ, cảnh sát được lệnh phải đi tuần mỗi ngày đúng một lần trên mỗi đường tắt.

Việc mở đường tắt theo phương án ), độ dài đường tuần tra sẽ là , với phương án ) là , còn với phương án ) là .

Yêu cầu: Cho và cặp tiểu khu xác định các đường hiện có. Hãy xác định độ dài đường tuần tra nếu đường tắt được mở tối ưu.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên và ;
• Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và xác định một con đường.

Dữ liệu ra:

• Ghi ra một số nguyên là độ dài đường tuần tra ngắn nhất nếu mở thêm đường tắt.

Ví dụ:

Dữ liệu vào:

8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6

Dữ liệu ra:

11

Giới hạn:

• Trong tất cả các test có .
• số test có .
• số test có K = 1.
• số test, mỗi làng có số đường trực tiếp tối đa .
• số test, mỗi làng có số đường trực tiếp tối đa .