You are given a list of allowed itineraries between cities. Each itinerary represents a directed route from one city to another city.

Design an algorithm to find the longest route that can be formed using the given itineraries. A route may start from any city and must follow only the given directed itineraries.

The length of a route is measured by the number of cities visited in that route. Return the route that visits the maximum number of cities.

Route Format

• Each itinerary is represented as a string in the format "source,destination".
• For example, "Mumbai,Pune" means there is a directed route from Mumbai to Pune.
• The returned route should be a string where city names are separated by "->".
• For example, "Mumbai->Pune->Delhi".

Rules

• The graph formed by the allowed itineraries will not contain any directed cycle.
• If multiple longest routes have the same number of cities, return the lexicographically smallest route string.
• If no itinerary is present, return an empty string.

Methods

String findLongestItineraryRoute(List<String> allowedItineraries)

Constraints

• 0 ≤ allowedItineraries.size() ≤ 100,000
• 1 ≤ source.length() ≤ 100
• 1 ≤ destination.length() ≤ 100
• source != destination for every itinerary string.
• Each itinerary string contains exactly one comma character.
• City names will not contain a comma character.
• City names will not start or end with a space.
• City names may contain English letters, digits, spaces, hyphens, and underscores.

Examples

Example 1

Method call:

findLongestItineraryRoute(allowedItineraries = List.of("Mumbai,Pune", "Pune,Indore", "Indore,Delhi", "Pune,Delhi"))

Output:

"Mumbai->Pune->Indore->Delhi"

Explanation:

The route visits 4 cities, which is the maximum possible.

Example 2

Method call:

findLongestItineraryRoute(allowedItineraries = List.of("A,B", "A,C", "B,D", "C,D"))

Output:

"A->B->D"

Explanation:

Both A->B->D and A->C->D visit 3 cities. Since "A->B->D" is lexicographically smaller, it is returned.

Example 3

Method call:

findLongestItineraryRoute(allowedItineraries = List.of("Delhi,Agra", "Goa,Mumbai", "Mumbai,Pune", "Pune,Nashik"))

Output:

"Goa->Mumbai->Pune->Nashik"

Explanation:

The input contains disconnected groups of cities. The returned route visits the maximum number of cities.

Example 4

Method call:

findLongestItineraryRoute(allowedItineraries = List.of("A,B", "A,B", "B,C"))

Output:

"A->B->C"

Explanation:

The duplicate itinerary "A,B" is treated as a single directed itinerary.

Example 5

Method call:

findLongestItineraryRoute(allowedItineraries = List.of())

Output:

""

Explanation:

There are no allowed itineraries, so no route can be formed.