A travel agent wants to plan the trips (one way) in such a way that he makes a maximum profit in the journey fares by maximizing the total travel distance of all couples. Help him plan the trips for all couples such that he maximizes the total distances traveled by all couples.
The travel distance of a couple is the distance between the city he lives in and the city he travels to. These N cities have N-1 highways connecting them. Travelers always choose the shortest path when traveling.

Can anyone solve this question?