<s> class Solution ( object ) : <EOL> def findItinerary ( self , tickets ) : <EOL> """<STR_LIT>""" <EOL> def route_helper ( origin , ticket_cnt , graph , ans ) : <EOL> if ticket_cnt == <NUM_LIT:0> : <EOL> return True <EOL> for i , ( dest , valid ) in enumerate ( graph [ origin ] ) : <EOL> if valid : <EOL> graph [ origin ] [ i ] [ <NUM_LIT:1> ] = False <EOL> ans . append ( dest ) <EOL> if route_helper ( dest , ticket_cnt - <NUM_LIT:1> , graph , ans ) : <EOL> return ans <EOL> ans . pop ( ) <EOL> graph [ origin ] [ i ] [ <NUM_LIT:1> ] = True <EOL> return False <EOL> graph = collections . defaultdict ( list ) <EOL> for ticket in tickets : <EOL> graph [ ticket [ <NUM_LIT:0> ] ] . append ( [ ticket [ <NUM_LIT:1> ] , True ] ) <EOL> for k in graph . keys ( ) : <EOL> graph [ k ] . sort ( ) <EOL> origin = "<STR_LIT>" <EOL> ans = [ origin ] <EOL> route_helper ( origin , len ( tickets ) , graph , ans ) <EOL> return ans </s>
