Use Every Ticket

You hold a pile of one-way plane tickets, each a pair [from, to] of airport codes, and you want one trip that starts at the airport start and uses every ticket exactly once, each flight leaving from the airport where the one before it landed.

Write plan_trip(tickets, start) that returns the trip as a list of airports that begins with start, so it holds one more airport than there are tickets. If several trips use every ticket, return the one that comes first alphabetically when you compare the trips airport by airport, the way Python compares lists.

Examples

plan_trip([['LIS', 'MAD'], ['MAD', 'ROM'], ['ROM', 'LIS'], ['LIS', 'ATH']], 'LIS')
# returns ['LIS', 'MAD', 'ROM', 'LIS', 'ATH']
plan_trip([['OSL', 'BER'], ['BER', 'OSL'], ['OSL', 'CPH'], ['CPH', 'OSL']], 'OSL')
# returns ['OSL', 'BER', 'OSL', 'CPH', 'OSL']
plan_trip([['NBO', 'CAI']], 'NBO')  # returns ['NBO', 'CAI']

In the first example the trip cannot begin with the flight to 'ATH', even though Athens comes first alphabetically: no ticket leaves Athens, so the other three tickets would never be used.

Constraints

• 1 to 20,000 tickets. Airport codes are strings of capital letters and digits.
• The same ticket can appear several times, and each copy must be used once.
• The tickets always allow at least one trip from start that uses them all.

Note

• A trip can be 20,000 flights long. Python stops recursion at about 1,000 levels, so a recursive search has to be rewritten with a stack of your own.