/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 * // @return true if this NestedInteger holds a single integer, rather than a
 * nested list.
 * public boolean isInteger();
 *
 * // @return the single integer that this NestedInteger holds, if it holds a
 * single integer
 * // Return null if this NestedInteger holds a nested list
 * public Integer getInteger();
 *
 * // @return the nested list that this NestedInteger holds, if it holds a
 * nested list
 * // Return empty list if this NestedInteger holds a single integer
 * public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    private List<Integer> list;
    private int ptr;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = new ArrayList<>();
        for (NestedInteger e : nestedList) {
            expand(list, e);
        }
    }

    @Override
    public Integer next() {
        return list.get(ptr++);
    }

    @Override
    public boolean hasNext() {
        return ptr < list.size();
    }

    private void expand(List<Integer> list, NestedInteger nestedInteger) {
        if (nestedInteger.isInteger()) {
            list.add(nestedInteger.getInteger());
            return;
        }
        for (NestedInteger e : nestedInteger.getList()) {
            expand(list, e);
        }
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

class Solution {
    private int ans;

    public int longestPath(int[] parent, String s) {
        ans = 1;
        Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
        for (int i = 1; i < parent.length; i++) {
            int currNode = i, currNodeParent = parent[i];
            nodeNeighbors.computeIfAbsent(currNodeParent, (key) -> new ArrayList<>()).add(currNode);
        }
        dfs(0, nodeNeighbors, s.toCharArray());
        return ans;
    }

    private int dfs(int currNode, Map<Integer, List<Integer>> nodeNeighbors, char[] nodeChar) {
        int currNodeMaxPath = 1;
        if (nodeNeighbors.containsKey(currNode)) {
            int maxOne = 0, maxTwo = 0;
            for (int neighbor : nodeNeighbors.get(currNode)) {
                char neighborChar = nodeChar[neighbor];
                int subtreeMaxPath = dfs(neighbor, nodeNeighbors, nodeChar);
                if (neighborChar != nodeChar[currNode]) {
                    if (subtreeMaxPath > maxTwo) {
                        maxOne = maxTwo;
                        maxTwo = subtreeMaxPath;
                    } else if (subtreeMaxPath > maxOne) {
                        maxOne = subtreeMaxPath;
                    }
                }
            }
            ans = Math.max(ans, maxOne + maxTwo + 1);
            currNodeMaxPath = maxTwo + 1;
        }
        return currNodeMaxPath;
    }
}

class Solution {
    private int[] ans;

    public int[] countSubTrees(int n, int[][] edges, String labels) {
        Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
        for (int[] edge : edges) {
            nodeNeighbors.computeIfAbsent(edge[0], (key) -> new ArrayList<>()).add(edge[1]);
            nodeNeighbors.computeIfAbsent(edge[1], (key) -> new ArrayList<>()).add(edge[0]);
        }
        ans = new int[n];
        dfs(0, -1, labels.toCharArray(), nodeNeighbors);
        return ans;
    }

    private int[] dfs(int currNode, int parent, char[] labels, Map<Integer, List<Integer>> nodeNeighbors) {
        int[] subtreeLabelCount = new int[26];
        for (int neighbor : nodeNeighbors.get(currNode)) {
            if (neighbor != parent) {
                mergeArray(subtreeLabelCount, dfs(neighbor, currNode, labels, nodeNeighbors));
            }
        }
        int currNodeLabelCount = ++subtreeLabelCount[labels[currNode] - 'a'];
        ans[currNode] = currNodeLabelCount;
        return subtreeLabelCount;
    }

    private void mergeArray(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] += arr2[i];
        }
    }
}

class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
        for (int[] edge : edges) {
            nodeNeighbors.computeIfAbsent(edge[0], (key) -> new ArrayList<>()).add(edge[1]);
            nodeNeighbors.computeIfAbsent(edge[1], (key) -> new ArrayList<>()).add(edge[0]);
        }
        int path = dfs(0, nodeNeighbors, hasApple, new HashSet<>());
        return path == 0 ? path : path - 2;
    }

    private int dfs(int currNode, Map<Integer, List<Integer>> nodeNeighbors, List<Boolean> hasApple,
            Set<Integer> visited) {
        visited.add(currNode);
        int path = 0;
        for (int neighbor : nodeNeighbors.get(currNode)) {
            if (!visited.contains(neighbor)) {
                int subtreePath = dfs(neighbor, nodeNeighbors, hasApple, visited);
                path += subtreePath;

            }
        }
        if (hasApple.get(currNode) || path != 0) {
            path += 2;
        }
        visited.remove(currNode);
        return path;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public boolean checkEqualTree(TreeNode root) {
        Map<Integer, Integer> sumCount = new HashMap<>();
        int treeSum = dfs(root, sumCount);
        if (treeSum % 2 != 0)
            return false;
        int targetSumCount = sumCount.getOrDefault(treeSum / 2, 0);
        return targetSumCount >= 2 || (targetSumCount == 1 && treeSum != 0);
    }

    private int dfs(TreeNode node, Map<Integer, Integer> sumCount) {
        if (node == null)
            return 0;
        int sum = node.val + dfs(node.left, sumCount) + dfs(node.right, sumCount);
        sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
        return sum;
    }
}

class Solution {
    public int minimumRounds(int[] tasks) {
        Map<Integer, Integer> taskCount = new HashMap<>();
        for (int task : tasks) {
            taskCount.put(task, taskCount.getOrDefault(task, 0) + 1);
        }
        int totalRound = 0;
        for (Integer count : taskCount.values()) {
            if (count == 1) {
                return -1;
            }
            if (count % 3 == 0) {
                totalRound += (count / 3);
            } else if (count % 3 == 1) {
                totalRound += ((count / 3) + 1);
            } else {
                totalRound += ((count / 3) + 1);
            }
        }
        return totalRound;
    }
}

class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        return backtrack(pattern, s, 0, 0, new HashMap<>(), new HashSet<>());
    }

    private boolean backtrack(String pattern, String s, int patternPtr, int sPtr, Map<Character, String> letterMapping,
            Set<String> visited) {
        if (patternPtr >= pattern.length() && sPtr >= s.length()) {
            return true;
        }
        if (patternPtr >= pattern.length() || sPtr >= s.length()) {
            return false;
        }
        char currLetter = pattern.charAt(patternPtr);
        if (letterMapping.containsKey(currLetter)) {
            String targetWord = letterMapping.get(currLetter);
            if (targetWord.length() > (s.length() - sPtr)
                    || !targetWord.equals(s.substring(sPtr, sPtr + targetWord.length()))) {
                return false;
            } else {
                return backtrack(pattern, s, patternPtr + 1, sPtr + targetWord.length(), letterMapping, visited);
            }
        } else {
            for (int i = sPtr + 1; i <= s.length(); i++) {
                String currWord = s.substring(sPtr, i);
                if (!visited.contains(currWord)) {
                    visited.add(currWord);
                    letterMapping.put(currLetter, currWord);
                    if (backtrack(pattern, s, patternPtr + 1, sPtr + currWord.length(), letterMapping, visited)) {
                        return true;
                    }
                    letterMapping.remove(currLetter);
                    visited.remove(currWord);
                }
            }
        }
        return false;
    }
}

class Solution {
    public int[] getOrder(int[][] tasks) {
        int[][] taskIndex = new int[tasks.length][3];
        for (int i = 0; i < tasks.length; i++) {
            // Index
            taskIndex[i][0] = i;
            // Enqueue Time
            taskIndex[i][1] = tasks[i][0];
            // Processing Time
            taskIndex[i][2] = tasks[i][1];
        }
        Arrays.sort(taskIndex, (a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
        // 0 is the index, 1 is the processing time
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
        int[] ans = new int[tasks.length];
        int ansPtr = 0, taskPtr = 0, currTime = 0;
        while (ansPtr < ans.length) {
            while (taskPtr < taskIndex.length && taskIndex[taskPtr][1] <= currTime) {
                minHeap.offer(new int[] { taskIndex[taskPtr][0], taskIndex[taskPtr][2] });
                taskPtr += 1;
            }
            if (!minHeap.isEmpty()) {
                int[] currTask = minHeap.poll();
                ans[ansPtr] = currTask[0];
                currTime += currTask[1];
                ansPtr += 1;
            } else {
                currTime = taskIndex[taskPtr][1];
            }
        }
        return ans;
    }
}

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Deque<Integer> availableRooms = new ArrayDeque<>();
        boolean[] visited = new boolean[rooms.size()];
        visited[0] = true;
        availableRooms.offer(0);
        int roomCount = 1;
        while (!availableRooms.isEmpty()) {
            int currRoom = availableRooms.poll();
            for (Integer key : rooms.get(currRoom)) {
                if (!visited[key]) {
                    availableRooms.offer(key);
                    visited[key] = true;
                    roomCount += 1;
                }
            }
        }
        return roomCount == rooms.size();
    }
}

class Solution {
    private Integer[][] memo;

    public int minFallingPathSum(int[][] matrix) {
        memo = new Integer[matrix.length][matrix[0].length];
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < matrix[0].length; i++) {
            ans = Math.min(ans, backtrack(matrix, 0, i));
        }
        return ans;
    }

    private int backtrack(int[][] matrix, int row, int col) {
        if (memo[row][col] != null) {
            return memo[row][col];
        }
        if (row == matrix.length - 1) {
            return matrix[row][col];
        }
        int ans = matrix[row][col], minSubPath = Integer.MAX_VALUE;
        for (int i = -1; i <= 1; i++) {
            int newRow = row + 1, newCol = col + i;
            if (!isOutOfBound(matrix, newRow, newCol)) {
                minSubPath = Math.min(minSubPath, backtrack(matrix, newRow, newCol));
            }
        }
        return memo[row][col] = ans + minSubPath;
    }

    private boolean isOutOfBound(int[][] matrix, int row, int col) {
        return row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length;
    }
}