Đất nước ALPHA có thành phố và con đường hai chiều nối giữa các cặp thành phố với nhau đảm bảo sự đi lại giữa mọi cặp thanh phố.
Công ty BETA đã thắng trong cuộc đấu thầu để sửa chửa tuyến đường. Một tuyến đường là một dãy các thành phố khác nhau, liên kết với nhau bởi những con đường. Công ty được phép chọn tuyến đường bất kỳ để sửa, nhưng họ phải chọn tuyến đường không được giao nhau (tức là không có một thành phố trên cả tuyến đường đó).
Cho biết lợi nhuận của việc sửa mỗi con đường luôn bằng , lợi nhuận sửa chữa mỗi tuyến bằng tổng lợi nhuận sửa chữa các con đường trên tuyến đó. Lợi nhuận khi sửa chữa tuyến đường bằng tích của lợi nhuận mỗi tuyến.
Nhiệm vụ của bạn là giúp công ty BETA tìm tuyến đường để sửa sao cho lợi nhuận thu được là lớn nhất.
Dữ liệu vào:
Dòng đầu chứa số ;
dòng tiếp theo mỗi dòng chứa hai số nguyên thể hiện một con đường nối giữa và .
