class Solution {
    // 用双端队列存储最终结果，方便在两端进行操作
    public Deque<String> result = new LinkedList<>();

    // 使用 HashMap 存储航班信息，key 为出发机场，value 为到达机场以及相应航班的次数
    // TreeMap 保证到达机场按字典序排列
    public Map<String, Map<String, Integer>> map = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // 遍历机票信息，构建航班映射表
        for (List<String> t : tickets) {
            Map<String, Integer> temp;
            // 如果出发机场已经存在于 map 中，取出对应的到达机场映射
            if (map.containsKey(t.get(0))) {
                temp = map.get(t.get(0));
                // 更新到达机场的航班次数（允许重复航班）
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                // 如果出发机场不存在，创建一个 TreeMap 来保存到达机场，确保按字典序排序
                temp = new TreeMap<>(); // 升序
                temp.put(t.get(1), 1);
            }
            // 将更新后的到达机场映射存回 map
            map.put(t.get(0), temp);
        }

        // 起点是 "JFK"，将其加入结果路径
        result.add("JFK");

        // 开始回溯搜索，尝试找到一条完整的行程
        backtracking(tickets.size());

        // 将结果转换为 List 并返回
        return new ArrayList<>(result);
    }

    // 回溯函数，尝试构建完整行程
    public boolean backtracking(int ticketNum) {
        // 当路径中的节点数等于机票数加 1 时，说明已找到完整路径
        if (result.size() == ticketNum + 1) {
            return true;
        }

        // 获取当前路径最后一个机场
        String last = result.getLast();

        // 检查当前机场是否存在后续航班
        if (map.containsKey(last)) { // 防止空指针异常
            // 遍历所有从该机场出发的航班
            for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
                int count = target.getValue();
                // 如果还有未使用的航班
                if (count > 0) {
                    // 将该目的地加入结果路径
                    result.add(target.getKey());
                    // 更新该航班的剩余次数
                    target.setValue(count - 1);

                    // 递归调用，继续构建剩余行程
                    if (backtracking(ticketNum)) {
                        return true; // 如果找到可行路径，立即返回
                    }

                    // 回溯操作：移除最后一个添加的目的地，恢复航班次数
                    result.removeLast();
                    target.setValue(count);
                }
            }
        }

        // 如果没有找到有效路径，返回 false
        return false;
    }
}

class Solution {
    // 用于存储最终的行程结果
    private LinkedList<String> res;
    // 用于存储当前路径
    private LinkedList<String> path = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // 对机票按照目的地字母顺序进行排序，保证字典序最小的行程先被访问
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));

        // 起点是 "JFK"，将其加入路径中
        path.add("JFK");

        // 用来标记机票是否已被使用
        boolean[] used = new boolean[tickets.size()];

        // 开始回溯搜索，寻找符合条件的行程
        backTracking((ArrayList) tickets, used);

        // 返回最终结果
        return res;
    }

    // 回溯函数，用来寻找符合条件的行程
    public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
        // 当路径长度等于机票数量 + 1 时，说明找到了完整路径
        if (path.size() == tickets.size() + 1) {
            res = new LinkedList<>(path); // 将当前路径复制到结果中
            return true; // 返回 true 表示已找到结果，终止递归
        }

        // 遍历所有机票，尝试找到下一个符合条件的目的地
        for (int i = 0; i < tickets.size(); i++) {
            // 如果当前机票未被使用，且该机票的出发地与当前路径的最后一个机场相同
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                // 将目的地添加到路径中
                path.add(tickets.get(i).get(1));
                // 标记该机票已使用
                used[i] = true;

                // 递归调用，继续寻找下一站行程
                if (backTracking(tickets, used)) {
                    return true; // 如果找到了完整路径，直接返回 true
                }

                // 回溯操作：移除最后一个添加的目的地，并重置该机票的使用状态
                used[i] = false;
                path.removeLast();
            }
        }

        // 如果没有找到有效路径，返回 false
        return false;
    }
}