class solver_this{
  public:
    solver_this(vector<vector<string>> _tickets): tickets(_tickets) {}
    bool used_all(vector<int> used_ticket){
        for (auto u : used_ticket){
            if (u != 1)
                return false;
        }
        return true;
    }
    
    void bfs(vector<int> used_ticket, vector<string> path){
        if (used_all(used_ticket)){
            ports.push_back(path);
            return;
        }
        else{
            for(int i =0 ; i < tickets.size() ; ++i){
                if (used_ticket[i] == 0){
                    if (path.back() == tickets[i][0]){
                        used_ticket[i] = 1;
                        path.push_back(tickets[i][1]);
                        bfs(used_ticket, path);
                        
                        used_ticket[i] = 0;
                        path.pop_back();
                    }                    
                }
            }
        }
    }
    
    vector<string> picking_path(){
        sort(ports.begin(), ports.end());
        return *ports.begin();
    }
    
    private:
    vector<vector<string>> tickets;
    vector<vector<string>> ports;
};

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    solver_this solver(tickets);
    vector<int> used_ticket(tickets.size(), 0);
    vector<string> path = {"ICN"};
        
    solver.bfs(used_ticket, path);
    answer = solver.picking_path(); 
   
    return answer;
}