from collections import defaultdict

# Undirected
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

# Directed weighted
graph = defaultdict(list)
for u, v, w in edges:
    graph[u].append((v, w))

from collections import deque

def bfs(graph, start):
    visited = set([start])
    q = deque([start])

    while q:
        node = q.popleft()
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                q.append(nei)

# Level-by-level (when depth matters)
def bfs_levels(graph, start):
    visited = set([start])
    q = deque([start])
    depth = 0

    while q:
        for _ in range(len(q)):          # process one level at a time
            node = q.popleft()
            for nei in graph[node]:
                if nei not in visited:
                    visited.add(nei)
                    q.append(nei)
        depth += 1
    return depth

# Key: always check boundary AND visited before enqueuing
from collections import deque

def grid_bfs(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    dirs = [[1,0],[0,1],[-1,0],[0,-1]]

    def is_valid(r, c):
        return 0 <= r < rows and 0 <= c < cols

    visited = set([(start_r, start_c)])
    q = deque([(start_r, start_c, 0)])   # (row, col, dist)

    while q:
        r, c, dist = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            # TODO pattern: boundary AND visited checked together
            if is_valid(nr, nc) and (nr, nc) not in visited and grid[nr][nc] != WALL:
                visited.add((nr, nc))
                q.append((nr, nc, dist + 1))

# Walls and Gates pattern:
# When updating a cell's value IS the visited guard (overwrite only if better),
# you don't need a separate visited set.

from typing import List

def wallsAndGates(rooms: List[List[int]]) -> None:
    rows, cols = len(rooms), len(rooms[0])
    dirs = [[1,0],[0,1],[-1,0],[0,-1]]
    is_valid = lambda r, c: 0 <= r < rows and 0 <= c < cols and rooms[r][c] > 0

    def dfs(i, j, distance):
        for dr, dc in dirs:
            nr, nc = i + dr, j + dc
            # Branch cut: only recurse if this path improves the cell
            if is_valid(nr, nc) and rooms[nr][nc] > distance + 1:
                rooms[nr][nc] = distance + 1
                dfs(nr, nc, distance + 1)

    for i in range(rows):
        for j in range(cols):
            if rooms[i][j] == 0:
                dfs(i, j, 0)

from collections import defaultdict

# Recursive
def dfs_recursive(graph, root, visited=None):
    if visited is None:
        visited = set()
    visited.add(root)
    for child in graph[root]:
        if child not in visited:
            dfs_recursive(graph, child, visited)
    return visited

# Iterative (explicit stack)
def dfs_iterative(graph, root):
    visited = set()
    stack = [root]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for child in graph[node]:
            if child not in visited:
                stack.append(child)
    return visited

from collections import defaultdict

def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n
    count = 0

    def dfs(node):
        visited[node] = True
        for child in graph[node]:
            if not visited[child]:
                dfs(child)

    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1

    return count

# States: 0 = unvisited, 1 = in current path, 2 = fully processed
def has_cycle(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * n

    def dfs(node):
        visited[node] = 1
        for child in graph[node]:
            if visited[child] == 1:   # back edge → cycle
                return True
            if visited[child] == 2:   # already processed, safe
                continue
            if dfs(child):
                return True
        visited[node] = 2
        return False

    return any(dfs(i) for i in range(n) if visited[i] == 0)

from collections import defaultdict

def topo_dfs(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [False] * n
    stack = []

    def dfs(node):
        visited[node] = True
        for child in graph[node]:
            if not visited[child]:
                dfs(child)
        stack.append(node)   # push AFTER all children processed

    # Run on all nodes (handles forests)
    for i in range(n):
        if not visited[i]:
            dfs(i)

    return stack[::-1]   # reverse = topological order

from collections import defaultdict, deque

def kahn_topo(n, edges):
    graph = defaultdict(list)
    indegree = defaultdict(int)

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # Start with all 0-indegree nodes
    q = deque([i for i in range(n) if indegree[i] == 0])
    result = []

    while q:
        node = q.popleft()
        result.append(node)
        for child in graph[node]:
            indegree[child] -= 1
            if indegree[child] == 0:
                q.append(child)

    # If not all nodes processed → cycle exists
    return result if len(result) == n else []

import heapq
from collections import defaultdict

def dijkstra(n, times, source):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    pq = [(0, source)]
    dist = {}       # node → shortest dist (finalized when first popped)

    while pq:
        cost, node = heapq.heappop(pq)
        if node in dist:   # already finalized — skip
            continue
        dist[node] = cost
        for nei, weight in graph[node]:
            if nei not in dist:
                heapq.heappush(pq, (cost + weight, nei))

    # e.g. LC 743: all nodes reachable?
    return max(dist.values()) if len(dist) == n else -1

from collections import deque
from dataclasses import dataclass

KNIGHT_MOVES = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]

def knight_shortest_path(source, dest, N=8):
    def is_valid(x, y, visited):
        return 0 <= x < N and 0 <= y < N and (x, y) not in visited

    visited = set([source])
    q = deque([(source, 0)])

    while q:
        (x, y), dist = q.popleft()
        if (x, y) == dest:
            return dist
        for dx, dy in KNIGHT_MOVES:
            nx, ny = x + dx, y + dy
            if is_valid(nx, ny, visited):
                visited.add((nx, ny))
                q.append(((nx, ny), dist + 1))
    return -1

from collections import deque

def is_bipartite(graph):
    color = [0] * len(graph)

    def bfs(start):
        q = deque([(start, 1)])
        while q:
            node, c = q.popleft()
            color[node] = c
            for child in graph[node]:
                if color[child] == 0:
                    q.append((child, -c))
                elif color[child] == c:   # same color as parent → not bipartite
                    return False
        return True

    for i in range(len(graph)):
        if color[i] == 0 and not bfs(i):
            return False
    return True

# DFS variant
def is_bipartite_dfs(graph):
    color = [0] * len(graph)

    def dfs(node, c):
        color[node] = c
        for child in graph[node]:
            if color[child] == 0:
                if not dfs(child, -c):
                    return False
            elif color[child] == c:
                return False
        return True

    return all(color[i] != 0 or dfs(i, 1) for i in range(len(graph)))

from typing import List

def exist(board: List[List[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]

    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if board[r][c] != word[idx]:
            return False

        tmp, board[r][c] = board[r][c], '#'    # mark visited in-place
        found = any(dfs(r+dr, c+dc, idx+1) for dr, dc in dirs)
        board[r][c] = tmp                       # backtrack — restore cell
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

from collections import deque, defaultdict
from typing import List

# Build a route↔route graph: two routes are neighbors if they share a stop.
# BFS on routes (not stops) counts minimum bus changes.

def numBusesToDestination(routes: List[List[int]], source: int, target: int) -> int:
    if source == target:
        return 0

    routes = [set(r) for r in routes]

    # Build route graph: routes i and j are adjacent if they share a stop
    route_graph = defaultdict(set)
    for i in range(len(routes)):
        for j in range(i + 1, len(routes)):
            if routes[i] & routes[j]:           # shared stop
                route_graph[i].add(j)
                route_graph[j].add(i)

    # Seed BFS with all routes that include source
    visited_routes = set()
    q = deque()
    for i, route in enumerate(routes):
        if source in route:
            q.append((i, 1))
            visited_routes.add(i)

    while q:
        route_idx, buses = q.popleft()
        if target in routes[route_idx]:
            return buses
        for nei in route_graph[route_idx]:
            if nei not in visited_routes:
                visited_routes.add(nei)
                q.append((nei, buses + 1))

    return -1

from collections import defaultdict, deque

# Build an undirected graph from a binary tree, tagging edges with L/R/U.
# Then BFS to find the shortest path (with direction string) between two nodes.
# Pattern: LC 2096 — Step-By-Step Directions From a Binary Tree Node to Another

def getDirections(root, startValue, destValue):
    graph = defaultdict(list)   # node → [(neighbor, direction)]

    def build(node, parent, direction):
        if not node: return
        if parent:
            graph[parent.val].append((node.val, direction))   # parent → child
            graph[node.val].append((parent.val, "U"))         # child → parent (up)
        build(node.left,  node, "L")
        build(node.right, node, "R")

    build(root, None, "")

    # Standard BFS — accumulate direction string along the path
    visited = {startValue}
    q = deque([(startValue, "")])

    while q:
        node, path = q.popleft()
        if node == destValue:
            return path
        for child, direction in graph[node]:
            if child not in visited:
                visited.add(child)
                q.append((child, path + direction))