def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def is_valid_bst(root):
    def helper(node, lower, upper):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        return (helper(node.left, lower, node.val) and
                helper(node.right, node.val, upper))
    return helper(root, float('-inf'), float('inf'))

def max_path_sum(root):
    result = float('-inf')
    def helper(node):
        nonlocal result
        if not node:
            return 0
        left = max(helper(node.left), 0)
        right = max(helper(node.right), 0)
        result = max(result, left + right + node.val)
        return max(left, right) + node.val
    helper(root)
    return result

class Codec:
    def serialize(self, root):
        def helper(node):
            if not node:
                return ['#']
            return [str(node.val)] + helper(node.left) + helper(node.right)
        return ','.join(helper(root))

    def deserialize(self, data):
        vals = iter(data.split(','))
        def helper():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = helper()
            node.right = helper()
            return node
        return helper()

from collections import deque, defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    queue = deque([i for i in range(num_courses) if indegree[i] == 0])
    count = 0
    while queue:
        course = queue.popleft()
        count += 1
        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                queue.append(next_course)
    return count == num_courses

from collections import deque

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

def clone_graph(node):
    if not node:
        return None
    visited = {}
    queue = deque([node])
    visited[node] = Node(node.val)
    while queue:
        curr = queue.popleft()
        for neighbor in curr.neighbors:
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            visited[curr].neighbors.append(visited[neighbor])
    return visited[node]

def find_judge(n, trust):
    indegree = [0] * (n + 1)
    outdegree = [0] * (n + 1)
    for a, b in trust:
        outdegree[a] += 1
        indegree[b] += 1
    for i in range(1, n + 1):
        if indegree[i] == n - 1 and outdegree[i] == 0:
            return i
    return -1

def pacific_atlantic(heights):
    if not heights:
        return []
    rows, cols = len(heights), len(heights[0])
    pacific = [[False] * cols for _ in range(rows)]
    atlantic = [[False] * cols for _ in range(rows)]

    def dfs(r, c, visited, prev_height):
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            visited[r][c] or heights[r][c] < prev_height):
            return
        visited[r][c] = True
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dfs(r + dr, c + dc, visited, heights[r][c])

    for i in range(rows):
        dfs(i, 0, pacific, 0)
        dfs(i, cols - 1, atlantic, 0)
    for j in range(cols):
        dfs(0, j, pacific, 0)
        dfs(rows - 1, j, atlantic, 0)

    result = []
    for i in range(rows):
        for j in range(cols):
            if pacific[i][j] and atlantic[i][j]:
                result.append([i, j])
    return result