class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        Map<Integer, Integer> reachableNode1 = new HashMap<>();
        Map<Integer, Integer> reachableNode2 = new HashMap<>();
        dfs(reachableNode1, node1, new boolean[edges.length], edges, 0);
        dfs(reachableNode2, node2, new boolean[edges.length], edges, 0);
        int distance = Integer.MAX_VALUE, targetNode = -1;
        for (Map.Entry<Integer, Integer> entry : reachableNode1.entrySet()) {
            int reachable1 = entry.getKey(), steps1 = entry.getValue();
            if (reachableNode2.containsKey(reachable1)) {
                int steps2 = reachableNode2.get(reachable1);
                int currMax = Math.max(steps1, steps2);
                if (currMax < distance || (currMax == distance && reachable1 < targetNode)) {
                    distance = currMax;
                    targetNode = reachable1;
                }
            }
        }
        return targetNode;
    }

    private void dfs(Map<Integer, Integer> nodeDistance, int currNode, boolean[] visited, int[] edges, int steps) {
        visited[currNode] = true;
        nodeDistance.put(currNode, steps);
        int nextNode = edges[currNode];
        if (nextNode != -1 && !visited[nextNode]) {
            dfs(nodeDistance, nextNode, visited, edges, steps + 1);
        }
    }
}

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length, boardSize = n * n;
        boolean[] visited = new boolean[n * n + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        visited[1] = true;
        queue.offer(1);
        int steps = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int currLabel = queue.poll();
                int rangeMax = Math.min(currLabel + 6, boardSize);
                for (int j = currLabel + 1; j <= rangeMax; j++) {
                    int nextLabel = j;
                    int nextLabelRow = getRow(n, nextLabel), nextLabelCol = getCol(n, nextLabel);
                    if (board[nextLabelRow][nextLabelCol] != -1) {
                        nextLabel = board[nextLabelRow][nextLabelCol];
                        nextLabelRow = getRow(n, nextLabel);
                        nextLabelCol = getCol(n, nextLabel);
                    }
                    if (!visited[nextLabel]) {
                        if (nextLabel == boardSize) {
                            return steps + 1;
                        } else {
                            visited[nextLabel] = true;
                            queue.offer(nextLabel);
                        }
                    }
                }
            }
            steps += 1;
        }
        return -1;
    }

    private int getRow(int n, int label) {
        return (n - 1) - (label - 1) / n;
    }

    private int getCol(int n, int label) {
        return ((label - 1) / n) % 2 == 0 ? (label - 1) % n : (n - 1) - (label - 1) % n;
    }
}

class Solution {
    private int ptr;

    public boolean isValidSerialization(String preorder) {
        ptr = 0;
        String[] nodes = preorder.split(",");
        return dfs(nodes) && ptr == nodes.length;
    }

    private boolean dfs(String[] preorder) {
        int localPtr = ptr;
        if (ptr == preorder.length)
            return false;
        if (preorder[ptr].equals("#")) {
            ptr += 1;
            return true;
        }
        ptr += 1;
        return dfs(preorder) && dfs(preorder);
    }
}

class Solution {
    private List<List<Integer>> ans;

    public List<List<Integer>> findSubsequences(int[] nums) {
        ans = new ArrayList<>();
        backtrack(new ArrayList<>(), nums, 0);
        return ans;
    }

    private void backtrack(List<Integer> currComb, int[] nums, int ptr) {
        Set<Integer> used = new HashSet<>();
        for (int i = ptr; i < nums.length; i++) {
            if (!used.contains(nums[i]) && (currComb.isEmpty() || nums[i] >= currComb.get(currComb.size() - 1))) {
                currComb.add(nums[i]);
                if (currComb.size() > 1) {
                    ans.add(new ArrayList<>(currComb));
                }
                backtrack(currComb, nums, i + 1);
                currComb.remove(currComb.size() - 1);
                used.add(nums[i]);
            }
        }
    }
}

/**
 * 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 {
    private List<Integer> leftBound;
    private List<Integer> rightBound;
    private List<Integer> leaves;

    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        leftBound = new ArrayList<>();
        rightBound = new ArrayList<>();
        leaves = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        ans.add(root.val);
        if (root.left != null) {
            dfs(root.left, -1);
        }
        if (root.right != null) {
            dfs(root.right, 1);
        }
        for (int node : leftBound) {
            ans.add(node);
        }
        for (int node : leaves) {
            ans.add(node);
        }
        for (int node : rightBound) {
            ans.add(node);
        }
        return ans;
    }

    private void dfs(TreeNode node, int status) {
        if (node == null)
            return;
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
        } else if (status == -1) {
            leftBound.add(node.val);
            if (node.left != null) {
                dfs(node.left, -1);
                dfs(node.right, 0);
            } else {
                dfs(node.right, -1);
            }
        } else if (status == 1) {
            rightBound.add(0, node.val);
            if (node.right != null) {
                dfs(node.left, 0);
                dfs(node.right, 1);
            } else {
                dfs(node.left, 1);
            }
        } else {
            dfs(node.left, 0);
            dfs(node.right, 0);
        }
    }
}

class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        Map<Integer, Map<Integer, Integer>> rowNonZeroPos = new HashMap<>();
        for (int row = 0; row < mat1.length; row++) {
            Map<Integer, Integer> currRowMap = new HashMap<>();
            for (int col = 0; col < mat1[0].length; col++) {
                if (mat1[row][col] != 0) {
                    currRowMap.put(col, mat1[row][col]);
                }
            }
            rowNonZeroPos.put(row, currRowMap);
        }
        int[][] ans = new int[mat1.length][mat2[0].length];
        for (int row = 0; row < ans.length; row++) {
            Map<Integer, Integer> currRowMap = rowNonZeroPos.get(row);
            for (int col = 0; col < ans[0].length; col++) {
                int currPosValue = 0;
                for (Map.Entry<Integer, Integer> entry : currRowMap.entrySet()) {
                    if (mat2[entry.getKey()][col] != 0) {
                        currPosValue += (mat2[entry.getKey()][col] * entry.getValue());
                    }
                }
                ans[row][col] = currPosValue;
            }
        }
        return ans;
    }
}

class Solution {
    public int minFlipsMonoIncr(String s) {
        int[] postCount = new int[s.length()];
        int zeroCount = 0;
        for (int i = postCount.length - 1; i >= 0; i--) {
            zeroCount += s.charAt(i) == '0' ? 1 : 0;
            postCount[i] = zeroCount;
        }
        int minFlips = Integer.MAX_VALUE, flipToZeroCount = 0;
        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);
            minFlips = Math.min(minFlips, postCount[i] + flipToZeroCount);
            if (letter == '1') {
                flipToZeroCount += 1;
            }
        }
        return Math.min(minFlips, flipToZeroCount);
    }
}

class Solution {
    public int numSteps(String s) {
        int steps = 0;
        boolean hasCarry = false;
        for (int i = s.length() - 1; i > 0; i--) {
            char currLetter = s.charAt(i);
            if (hasCarry) {
                if (currLetter == '0') {
                    currLetter = '1';
                    hasCarry = false;
                } else {
                    currLetter = '0';
                }
            }
            if (currLetter == '0') {
                steps += 1;
            } else {
                steps += 2;
                hasCarry = true;
            }
        }
        return hasCarry ? steps + 1 : steps;
    }
}

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        int ans = 0;
        Map<Integer, Integer> reservedRow = new HashMap<>();
        for (int[] reservedSeat : reservedSeats) {
            reservedRow.put(reservedSeat[0] - 1,
                    reservedRow.getOrDefault(reservedSeat[0] - 1, 0) | (1 << (reservedSeat[1] - 1)));
        }
        for (int currRowSeatStatus : reservedRow.values()) {
            if (currRowSeatStatus == 0) {
                ans += 2;
                continue;
            }
            boolean leftFree = true, middleFree = true, rightFree = true;
            // 0 1 1 | 1 1 0 0 | 0 0 0
            if ((currRowSeatStatus & 0x1e) != 0)
                leftFree = false;
            // 0 0 0 | 1 1 1 1 | 0 0 0
            if ((currRowSeatStatus & 0x78) != 0)
                middleFree = false;
            // 0 0 0 | 0 0 1 1 | 1 1 0
            if ((currRowSeatStatus & 0x1e0) != 0)
                rightFree = false;
            if (leftFree && rightFree) {
                ans += 2;
            } else if (leftFree || rightFree || middleFree) {
                ans += 1;
            }
        }
        return ans + 2 * (n - reservedRow.size());
    }
}

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        Map<Character, Set<Character>> nodeNeighbors = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char letterOne = s1.charAt(i), letterTwo = s2.charAt(i);
            nodeNeighbors.computeIfAbsent(letterOne, (key) -> new HashSet<>()).add(letterTwo);
            nodeNeighbors.computeIfAbsent(letterTwo, (key) -> new HashSet<>()).add(letterOne);
        }
        Map<Character, Character> letterMinCharMapping = new HashMap<>();
        StringBuilder ans = new StringBuilder();
        for (char letter : baseStr.toCharArray()) {
            if (!nodeNeighbors.containsKey(letter)) {
                ans.append(letter);
                continue;
            }
            if (!letterMinCharMapping.containsKey(letter)) {
                StringBuilder nodes = new StringBuilder();
                char minChar = getMinChar(letter, nodeNeighbors, nodes, new HashSet<>());
                store(letterMinCharMapping, minChar, nodes.toString());
            }
            ans.append(letterMinCharMapping.get(letter));
        }
        return ans.toString();
    }

    private char getMinChar(char letter, Map<Character, Set<Character>> nodeNeighbors, StringBuilder nodes,
            Set<Character> visited) {
        char currMinChar = letter;
        nodes.append(letter);
        for (char neighbor : nodeNeighbors.get(letter)) {
            if (visited.contains(neighbor))
                continue;
            visited.add(neighbor);
            char minChar = getMinChar(neighbor, nodeNeighbors, nodes, visited);
            if (minChar < currMinChar) {
                currMinChar = minChar;
            }
        }
        return currMinChar;
    }

    private void store(Map<Character, Character> letterMinCharMapping, char minChar, String nodes) {
        for (char node : nodes.toCharArray()) {
            letterMinCharMapping.put(node, minChar);
        }
    }
}