Find a Canonical Shortest Round Trip Through Flights

Problem Statement

You are given a list of directed flights, where each flight is represented as a pair of airport codes [origin, destination], and a start_airport. A round trip is a sequence of airports starting at start_airport, following available directed flights, and returning to start_airport.

Your task is to find a round trip that:

1. Uses the minimum number of flights (edges).
2. If multiple round trips tie for the minimum number of flights, choose the one that is lexicographically smallest as a sequence of airport codes.

If no round trip is possible, return an empty list [].

Note:

• A flight directly from start_airport to start_airport (a self-loop) is valid and counts as a round trip of length 1 (i.e., [start_airport, start_airport]).
• Flights may contain duplicate pairs. A flight can only be traversed in its specified direction.

Function Signature

def find_canonical_round_trip(flights: list[list[str]], start_airport: str) -> list[str]:
    pass

Constraints

• 1 <= len(flights) <= 20,000
• Each flight contains exactly two strings: [origin, destination]
• Each airport code is a string of 3 uppercase English letters (e.g., "JFK", "LAX")
• start_airport is a 3-letter uppercase English string

Examples

Example 1

flights = [
    ["JFK", "ORD"],
    ["ORD", "LAX"],
    ["LAX", "JFK"],
    ["JFK", "DFW"],
    ["DFW", "LAX"]
]
start_airport = "JFK"

# Output: ["JFK", "DFW", "LAX", "JFK"]

Explanation: There are two round trips of length 3 hops:

• ["JFK", "ORD", "LAX", "JFK"]
• ["JFK", "DFW", "LAX", "JFK"] Both have 3 hops. Comparing them lexicographically, "DFW" < "ORD", so ["JFK", "DFW", "LAX", "JFK"] is returned.

Example 2

flights = [
    ["SFO", "SEA"],
    ["SEA", "SFO"],
    ["SFO", "DEN"],
    ["DEN", "SFO"],
    ["SFO", "SFO"]
]
start_airport = "SFO"

# Output: ["SFO", "SFO"]

Explanation: The self-loop ["SFO", "SFO"] requires only 1 hop, which is strictly shorter than any 2-hop route.

Example 3

flights = [
    ["MIA", "ATL"],
    ["ATL", "BOS"]
]
start_airport = "MIA"

# Output: []

Explanation: It is impossible to return to "MIA", so return [].