Giáo sư X cảm thấy mệt mỏi với công việc giảng dạy và nghiên cứu nên ông quyết định vác xe đi dạo quanh các con đường trong thành phố để thay đổi không khí. Có địa điểm đánh số từ tới và con đường một chiều đánh số từ tới . Con đường thứ cho phép đi từ địa điểm tới địa điểm và có độ dài . Hệ thống đường cho phép đi lại giữa hai địa điểm bất kỳ.
Giáo sư X xuất phát từ trường nằm tại địa điểm . Ông muốn đi qua tất cả con đường rồi sau đó quay trở về trường. Ông có thể đi qua một con đường nhiều lần nhưng buộc phải đi theo chiều đã định của những con đường, bởi nếu đi ngược chiều thì ông sẽ được hưởng vài giờ nghỉ bất đắc dĩ tại trụ sở cảnh sát giao thông.
Yêu cầu: Tìm hành trình ngắn nhất cho giáo sư X thỏa mãn yêu cầu trên.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương ;
dòng tiếp theo, dòng thứ chứa ba số nguyên dương .
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là độ dài hành trình tìm được.
