Hai đường đặc biệt
Đề bài
Mô tả
Để biến Thành phố Tuyệt vời thành nơi hấp dẫn hơn với du khách, chính quyền đưa ra kế hoạch sau: chọn hai con đường của thành phố và gọi chúng là các ĐƯỜNG ĐẶC BIỆT. Các đường đặc biệt này sẽ được công bố là những địa điểm cực kỳ quan trọng, thu hút du khách khắp thế giới.
Thành phố được biểu diễn bằng một đồ thị với các đỉnh là các ngã tư và các cạnh là các con đường nối hai ngã tư. Đồ thị có tổng cộng đỉnh và cạnh, mỗi con đường đi được theo cả hai chiều. Từ một ngã tư bất kỳ có thể đi tới mọi ngã tư khác chỉ bằng các con đường. Mỗi con đường nối hai ngã tư khác nhau và không có hai con đường nào nối cùng một cặp ngã tư.
Để giảm lưu lượng trên các đường đặc biệt, người ta quyết định thu phí trên mỗi đường đặc biệt theo cả hai chiều: mỗi lần đi qua một đường đặc biệt phải trả đồng xu. Các con đường khác không mất phí.
Các nhà phân tích đã thu thập một mẫu gồm người dân, người thứ cần đi làm từ ngã tư tới ngã tư . Sau khi hai đường đặc biệt được chọn, mỗi người sẽ đi làm theo đường đi có chi phí nhỏ nhất.
Để thu được nhiều xu nhất, cần chọn hai con đường làm đường đặc biệt sao cho tổng số xu mà người dân này phải trả là lớn nhất. Hãy giúp chính quyền: với sơ đồ thành phố và mẫu người dân đã cho, hãy cho biết nên chọn hai con đường nào làm đường đặc biệt, và khi đó người dân sẽ trả tổng cộng bao nhiêu xu.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên , số bộ test.
Mỗi bộ test có dạng:
- Dòng đầu tiên chứa hai số nguyên và , số ngã tư và số con đường.
- dòng tiếp theo, dòng thứ chứa hai số nguyên và (, ) là hai ngã tư được nối bởi con đường thứ . Không có hai con đường nối cùng một cặp ngã tư, và từ một ngã tư bất kỳ có thể đi tới mọi ngã tư khác.
- Dòng tiếp theo chứa số nguyên , số người dân trong mẫu.
- dòng tiếp theo, dòng thứ chứa hai số nguyên và (, ): người thứ đi làm từ ngã tư tới ngã tư .
Dữ liệu ra
Với mỗi bộ test, in ra:
- Dòng thứ nhất: tổng số xu mà người dân phải trả.
- Dòng thứ hai: hai số nguyên , là hai ngã tư được nối bởi đường đặc biệt thứ nhất.
- Dòng thứ ba: hai số nguyên , là hai ngã tư được nối bởi đường đặc biệt thứ hai.
Hai ngã tư của mỗi đường đặc biệt có thể in theo thứ tự bất kỳ. Mỗi đường được in phải là một trong con đường của thành phố, và hai đường được chọn phải khác nhau. Nếu có nhiều cách chọn tối ưu, in cách bất kỳ.
Ràng buộc
- .
- , , .
- .
- Tổng trên mọi bộ test và tổng trên mọi bộ test đều không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 5 1 2 2 3 3 4 4 5 5 1 6 1 5 1 3 1 3 2 4 2 5 5 3 6 5 1 2 2 3 2 4 4 5 4 6 3 1 6 5 3 2 5 |
5 1 5 3 2 5 4 2 5 4 |
Bộ thứ nhất: chọn đường và thì vòng tròn bị cắt thành hai phần và ; năm người có hai đầu ở hai phần khác nhau mỗi người trả xu. Bộ thứ hai: chọn và , người đi trả xu, hai người còn lại mỗi người trả xu. (Đề gốc ghi nhầm .) |
| 1 3 2 1 2 2 3 2 1 3 2 3 |
3 1 2 2 3 |
Ví dụ bổ sung (không có trong đề gốc). Cả hai con đường đều được chọn: người đi trả xu, người đi trả xu. |
Bình luận