class Solution {
    public long countPairs(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        Map<Integer, List<Integer>> neighbors = new HashMap<>();
        for (int[] edge : edges) {
            neighbors.computeIfAbsent(edge[0], (key) -> new ArrayList<>()).add(edge[1]);
            neighbors.computeIfAbsent(edge[1], (key) -> new ArrayList<>()).add(edge[0]);
        }
        long ans = 0, remainingNodes = n;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                long groupSize = dfs(i, neighbors, visited);
                ans += groupSize * (remainingNodes - groupSize);
                remainingNodes -= groupSize;
            }
        }
        return ans;
    }

    private int dfs(int currNode, Map<Integer, List<Integer>> neighbors, boolean[] visited) {
        visited[currNode] = true;
        int ans = 1;
        if (!neighbors.containsKey(currNode)) {
            return ans;
        }
        for (Integer neighbor : neighbors.get(currNode)) {
            if (!visited[neighbor]) {
                ans += dfs(neighbor, neighbors, visited);
            }
        }
        return ans;
    }
}

class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> numPointMap = new HashMap<>();
        for (int num : nums) {
            numPointMap.put(num, numPointMap.getOrDefault(num, 0) + num);
        }
        List<Map.Entry<Integer, Integer>> numPointPairList = new ArrayList<>(numPointMap.entrySet());
        Collections.sort(numPointPairList, (a, b) -> Integer.compare(a.getKey(), b.getKey()));
        int first = 0, second = numPointPairList.get(0).getValue();
        for (int i = 1; i < numPointPairList.size(); i++) {
            int currNum = numPointPairList.get(i).getKey(), currValue = numPointPairList.get(i).getValue();
            int lastNum = numPointPairList.get(i - 1).getKey();
            if (currNum - 1 != lastNum) {
                int currMax = currValue + second;
                first = second;
                second = currMax;
            } else {
                int currMax = Math.max(currValue + first, second);
                first = second;
                second = currMax;
            }
        }
        return second;
    }
}

class Solution {
    public int singleNonDuplicate(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int leftCount = mid - left + 1;
            if (leftCount % 2 == 0) {
                if (nums[mid] == nums[mid - 1]) {
                    left = mid + 1;
                } else if (nums[mid] == nums[mid + 1]) {
                    right = mid - 1;
                } else {
                    return nums[mid];
                }
            } else {
                if (nums[mid] == nums[mid + 1]) {
                    left = mid + 2;
                } else if (nums[mid] == nums[mid - 1]) {
                    right = mid - 2;
                } else {
                    return nums[mid];
                }
            }
        }
        return nums[left];
    }
}

class Solution {
    public long minimumFuelCost(int[][] roads, int seats) {
        Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
        for (int[] road : roads) {
            nodeNeighbors.computeIfAbsent(road[0], (key) -> new ArrayList<>()).add(road[1]);
            nodeNeighbors.computeIfAbsent(road[1], (key) -> new ArrayList<>()).add(road[0]);
        }
        return minimumLiters(0, -1, nodeNeighbors, seats)[0];
    }

    // result[0] minimum liters, result[1] number of people at this city
    private long[] minimumLiters(int node, int parent, Map<Integer, List<Integer>> nodeNeighbors, int seats) {
        if (!nodeNeighbors.containsKey(node)) {
            return new long[] { 0, 1 };
        }
        long literCount = 0, peopleCount = 1;
        for (int neighbor : nodeNeighbors.get(node)) {
            if (neighbor == parent)
                continue;
            long[] neighborInfo = minimumLiters(neighbor, node, nodeNeighbors, seats);
            long carNeeded = neighborInfo[1] % seats == 0 ? neighborInfo[1] / seats : neighborInfo[1] / seats + 1;
            literCount += neighborInfo[0] + carNeeded;
            peopleCount += neighborInfo[1];
        }
        return new long[] { literCount, peopleCount };
    }
}

class Solution {
    // red -> 0, blue -> 1
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Map<Integer, List<int[]>> nodeNeighbors = new HashMap<>();
        for (int[] redEdge : redEdges) {
            int startNode = redEdge[0], endNode = redEdge[1];
            nodeNeighbors.computeIfAbsent(startNode, (key) -> new ArrayList<>()).add(new int[] { endNode, 0 });
        }
        for (int[] blueEdge : blueEdges) {
            int startNode = blueEdge[0], endNode = blueEdge[1];
            nodeNeighbors.computeIfAbsent(startNode, (key) -> new ArrayList<>()).add(new int[] { endNode, 1 });
        }
        Deque<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][2];
        visited[0][0] = true;
        visited[0][1] = true;
        queue.offer(new int[] { 0, -1 });
        int distance = 0;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        ans[0] = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int[] currNodeInfo = queue.poll();
                int currNode = currNodeInfo[0], lastEdgeColor = currNodeInfo[1];
                ans[currNode] = ans[currNode] == -1 ? distance : Math.min(ans[currNode], distance);
                if (nodeNeighbors.containsKey(currNode)) {
                    for (int[] neighborInfo : nodeNeighbors.get(currNode)) {
                        int neighbor = neighborInfo[0], pathColor = neighborInfo[1];
                        if (pathColor != lastEdgeColor && !visited[neighbor][pathColor]) {
                            visited[neighbor][pathColor] = true;
                            queue.offer(new int[] { neighbor, pathColor });
                        }
                    }
                }
            }
            distance += 1;
        }
        return ans;
    }
}

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        if (abbr.length() > word.length())
            return false;
        int ptr1 = 0, ptr2 = 0;
        while (ptr1 < word.length() && ptr2 < abbr.length()) {
            if (Character.isDigit(abbr.charAt(ptr2))) {
                if (abbr.charAt(ptr2) == '0')
                    return false;
                int currNum = 0;
                while (ptr2 < abbr.length() && Character.isDigit(abbr.charAt(ptr2))) {
                    currNum = currNum * 10 + abbr.charAt(ptr2) - '0';
                    ptr2 += 1;
                }
                if (ptr1 + currNum > word.length()) {
                    return false;
                } else {
                    ptr1 += currNum;
                }
            } else if (word.charAt(ptr1) != abbr.charAt(ptr2)) {
                return false;
            } else {
                ptr1 += 1;
                ptr2 += 1;
            }
        }
        return ptr1 == word.length() && ptr2 == abbr.length();
    }
}

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> nodeNeighbor = new HashMap<>();
        Map<Character, Integer> inDegreeCount = new HashMap<>();
        Set<Character> letterSet = new HashSet<>();
        addLetter(words[0], letterSet);
        for (int i = 1; i < words.length; i++) {
            addLetter(words[i], letterSet);
            int diffPos = findDiffPos(words[i - 1], words[i]);
            if (diffPos != -1) {
                char smallerLetter = words[i - 1].charAt(diffPos), biggerLetter = words[i].charAt(diffPos);
                if (!nodeNeighbor.containsKey(smallerLetter)
                        || !nodeNeighbor.get(smallerLetter).contains(biggerLetter)) {
                    nodeNeighbor.computeIfAbsent(smallerLetter, (key) -> new HashSet<>()).add(biggerLetter);
                    inDegreeCount.put(biggerLetter, inDegreeCount.getOrDefault(biggerLetter, 0) + 1);
                }
            } else if (words[i].length() < words[i - 1].length()) {
                return "";
            }
        }
        StringBuilder alienOrder = new StringBuilder();
        Deque<Character> nodes = new ArrayDeque<>();
        for (char letter : letterSet) {
            if (!inDegreeCount.containsKey(letter)) {
                nodes.offer(letter);
            }
        }
        while (!nodes.isEmpty()) {
            char currLetter = nodes.poll();
            alienOrder.append(currLetter);
            if (nodeNeighbor.containsKey(currLetter)) {
                for (char neighbor : nodeNeighbor.get(currLetter)) {
                    inDegreeCount.put(neighbor, inDegreeCount.get(neighbor) - 1);
                    if (inDegreeCount.get(neighbor) == 0) {
                        nodes.offer(neighbor);
                    }
                }
            }
        }
        return alienOrder.length() == letterSet.size() ? alienOrder.toString() : "";
    }

    private int findDiffPos(String str1, String str2) {
        if (str1.equals(str2))
            return -1;
        if (str1.length() > str2.length())
            return findDiffPos(str2, str1);
        int ptr1 = 0, ptr2 = 0;
        while (ptr1 < str1.length() && str1.charAt(ptr1) == str2.charAt(ptr2)) {
            ptr1 += 1;
            ptr2 += 1;
        }
        return ptr1 == str1.length() ? -1 : ptr1;
    }

    private void addLetter(String word, Set<Character> letterSet) {
        for (char letter : word.toCharArray()) {
            letterSet.add(letter);
        }
    }
}

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Integer> orderMap = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            orderMap.put(order.charAt(i), i);
        }
        for (int i = 1; i < words.length; i++) {
            if (compare(words[i - 1], words[i], orderMap) > 0)
                return false;
        }
        return true;
    }

    private int compare(String str1, String str2, Map<Character, Integer> orderMap) {
        if (str1.equals(str2))
            return 0;
        int ptr1 = 0, ptr2 = 0;
        while (ptr1 < str1.length() && ptr2 < str2.length()) {
            int letterOneOrder = orderMap.get(str1.charAt(ptr1)), letterTwoOrder = orderMap.get(str2.charAt(ptr2));
            if (letterOneOrder < letterTwoOrder) {
                return -1;
            } else if (letterOneOrder > letterTwoOrder) {
                return 1;
            } else {
                ptr1 += 1;
                ptr2 += 1;
            }
        }
        return ptr1 == str1.length() ? -1 : 1;
    }
}

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int[][] scoreAgePair = new int[scores.length][2];
        for (int i = 0; i < scoreAgePair.length; i++) {
            scoreAgePair[i][0] = scores[i];
            scoreAgePair[i][1] = ages[i];
        }
        Arrays.sort(scoreAgePair, (a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
        int[] dp = new int[scoreAgePair.length];
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = scoreAgePair[i][0];
            for (int j = 0; j < i; j++) {
                if (scoreAgePair[j][0] <= scoreAgePair[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + scoreAgePair[i][0]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}