<p>There is a <code>50 x 50</code> chessboard with <strong>one</strong> knight and some pawns on it. You are given two integers <code>kx</code> and <code>ky</code> where <code>(kx, ky)</code> denotes the position of the knight, and a 2D array <code>positions</code> where <code>positions[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> denotes the position of the pawns on the chessboard.</p>

<p>Alice and Bob play a <em>turn-based</em> game, where Alice goes first. In each player&#39;s turn:</p>

<ul>
	<li>The player <em>selects </em>a pawn that still exists on the board and captures it with the knight in the <strong>fewest</strong> possible <strong>moves</strong>. <strong>Note</strong> that the player can select <strong>any</strong> pawn, it <strong>might not</strong> be one that can be captured in the <strong>least</strong> number of moves.</li>
	<li><span>In the process of capturing the <em>selected</em> pawn, the knight <strong>may</strong> pass other pawns <strong>without</strong> capturing them</span>. <strong>Only</strong> the <em>selected</em> pawn can be captured in <em>this</em> turn.</li>
</ul>

<p>Alice is trying to <strong>maximize</strong> the <strong>sum</strong> of the number of moves made by <em>both</em> players until there are no more pawns on the board, whereas Bob tries to <strong>minimize</strong> them.</p>

<p>Return the <strong>maximum</strong> <em>total</em> number of moves made during the game that Alice can achieve, assuming both players play <strong>optimally</strong>.</p>

<p>Note that in one <strong>move, </strong>a chess knight has eight possible positions it can move to, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.</p>

<p><img src="https://assets.leetcode.com/uploads/2024/08/01/chess_knight.jpg" style="width: 275px; height: 273px;" /></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">kx = 1, ky = 1, positions = [[0,0]]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/16/gif3.gif" style="width: 275px; height: 275px;" /></p>

<p>The knight takes 4 moves to reach the pawn at <code>(0, 0)</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">8</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/08/16/gif4.gif" style="width: 320px; height: 320px;" /></strong></p>

<ul>
	<li>Alice picks the pawn at <code>(2, 2)</code> and captures it in two moves: <code>(0, 2) -&gt; (1, 4) -&gt; (2, 2)</code>.</li>
	<li>Bob picks the pawn at <code>(3, 3)</code> and captures it in two moves: <code>(2, 2) -&gt; (4, 1) -&gt; (3, 3)</code>.</li>
	<li>Alice picks the pawn at <code>(1, 1)</code> and captures it in four moves: <code>(3, 3) -&gt; (4, 1) -&gt; (2, 2) -&gt; (0, 3) -&gt; (1, 1)</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">kx = 0, ky = 0, positions = [[1,2],[2,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Alice picks the pawn at <code>(2, 4)</code> and captures it in two moves: <code>(0, 0) -&gt; (1, 2) -&gt; (2, 4)</code>. Note that the pawn at <code>(1, 2)</code> is not captured.</li>
	<li>Bob picks the pawn at <code>(1, 2)</code> and captures it in one move: <code>(2, 4) -&gt; (1, 2)</code>.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= kx, ky &lt;= 49</code></li>
	<li><code>1 &lt;= positions.length &lt;= 15</code></li>
	<li><code>positions[i].length == 2</code></li>
	<li><code>0 &lt;= positions[i][0], positions[i][1] &lt;= 49</code></li>
	<li>All <code>positions[i]</code> are unique.</li>
	<li>The input is generated such that <code>positions[i] != [kx, ky]</code> for all <code>0 &lt;= i &lt; positions.length</code>.</li>
</ul>

class Solution:
  def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
    graph = Grid(50, 50, grid_type=Grid.Type.kKnight)

    pawns = [graph.coor2idx(x, y) for [x, y] in positions]
    pawn_count = len(positions)

    costs = []
    for v in pawns:
      bfs = BFS(graph, ToTargets(pawns + [graph.coor2idx(kx, ky)]))
      bfs.run(v)
      costs.append(bfs.costs)

    @cache
    def minimax(visited, u):
      if visited.bit_count() == pawn_count:
        return 0
      if visited.bit_count() % 2 == 0:  # alice turn
        ans = 0
        op = max
      else:
        ans = math.inf
        op = min
      for i, v in enumerate(pawns):
        if not visited & (1 << i):
          ans = op(ans, minimax(visited | (1 << i), v) + costs[i][u])
      return ans
    
    return minimax(0, graph.coor2idx(kx, ky))


import math


from dataclasses import dataclass
from typing import Any


@dataclass
class Edge:
  source: int
  target: int
  attrs: Any = ()
  handle: Any = None


class Graph:
  """Graph ABC."""

  def __init__(self, vertex_count):
    """Initialize the graph with the given number of vertices."""
    assert vertex_count > 0
    self._vertex_count = vertex_count

  # --------------------------------------------------------------------------

  def add_undirected_edge(self, u: int, v: int, attrs=None, **kwargs):
    """Add an undirected edge between u and v with the given attributes.

    Returns: edge handles that can be used in `get` and 'remove' operations.
    """
    handle_uv = self.add_edge(u, v, attrs, **kwargs)
    handle_vu = self.add_edge(v, u, attrs, **kwargs)
    return handle_uv, handle_vu

  def add_edge(self, source: int, target: int, attrs=None, **kwargs):
    """Add a directed edge from source to target with given attributes.

    Returns: edge handle that can be used in `get` and 'remove' operations.
    """
    raise NotImplementedError()

  def get_edge(self, source: int, target: int, handle=None):
    """Retrieve a directed edge from source to target.

    Returns: Edge object.
    """
    raise NotImplementedError()

  def remove_edge(self, source: int, target: int, handle=None):
    """Remove a directed edge from source to target."""
    raise NotImplementedError()

  # --------------------------------------------------------------------------

  def out_edges(self, source: int):
    """Generate all outgoing edges from a given source vertex."""
    raise NotImplementedError()

  def in_edges(self, target: int):
    """Generate all incoming edges to a given target vertex."""
    for edge in self.edges():
      if edge.target == target:
        yield edge

  def edges(self):
    """Generate all edges in the graph."""
    for source in self.vertices():
      yield from self.out_edges(source)

  def vertices(self):
    """Generate all vertices in the graph."""
    return range(self._vertex_count)

  # --------------------------------------------------------------------------

  def out_degree(self, source: int) -> int:
    """Get the out-degree of a given source vertex."""
    return len(list(self.out_edges(source)))

  def out_degrees(self) -> list[int]:
    """Get the list of out-degrees of all vertices in the graph."""
    return [self.out_degree(source) for source in self.vertices()]

  def in_degree(self, target: int) -> int:
    """Get the in-degree of a given target vertex."""
    return len(list(self.in_edges(target)))

  def in_degrees(self) -> list[int]:
    """Get the list of in-degrees of all vertices in the graph."""
    in_degs = [0] * self.vertex_count()
    for edge in self.edges():
      in_degs[edge.target] += 1
    return in_degs

  # --------------------------------------------------------------------------

  def edge_count(self) -> int:
    """Get the number of edges in the graph."""
    return sum(self.out_degrees())

  def vertex_count(self) -> int:
    """Get the number of vertices in the graph."""
    return self._vertex_count

  # --------------------------------------------------------------------------

  def add_edges(self, edges):
    """Add directed edges with optional attributes."""
    for edge in edges:
      source, target, *attrs = edge
      self.add_edge(source, target, self._seq2attrs(attrs))

  def add_undirected_edges(self, edges):
    """Add undirected edges with optional attributes."""
    for edge in edges:
      source, target, *attrs = edge
      self.add_undirected_edge(source, target, self._seq2attrs(attrs))

  def _seq2attrs(self, attrs):
    match len(attrs):
      case 0: return Edge.attrs  # default empty tuple
      case 1: return attrs[0]
      case _: return attrs

  def _get_attrs(self, attrs, kwargs):
    """Build edge attrs object from `add_[undirected_]edge` method args."""
    if attrs is None:
      if kwargs is None:
        attrs = Edge.attrs
      else:
        # TODO: Convert to a named tuple?
        attrs = kwargs
    return attrs


def transposed(graph):
  """Transpose (reverse the direction of all edges in) the given graph."""
  transposed = type(graph)(graph.vertex_count())
  for source, target, attrs, _ in graph.edges():
    transposed.add_edge(target, source, attrs)
  return transposed


# ----------------------------------------------------------------------------
# Concrete Graph Classes
# ----------------------------------------------------------------------------


class AdjacencyList():

  def __init__(self):
    """Initialize an empty adjacency list."""
    self._out_edges = []
    self._size = 0

  def add(self, target: int, attrs) -> int:
    """Add a new edge to the end of the adjacency list.

    Returns: index of the added edge.
    """
    if len(self._out_edges) == self._size:
      self._out_edges.append((target, attrs))
    else:
      # assert len(self._out_edges) > self._size
      assert self._out_edges[self._size] is None
      self._out_edges[self._size] = (target, attrs)
    self._size += 1
    return self._size - 1

  def get(self, source: int, target: int, idx: int = None):
    """Retrieve an / the edge pointing at vertex `target`."""
    idx = self._index(target, idx)
    return Edge(source, target, self._out_edges[idx][1], idx)

  def remove(self, target: int, idx: int = None):
    """Remove an / the edge pointing at vertex `target`."""
    idx = self._index(target, idx)
    self._size -= 1
    self._out_edges[idx] = self._out_edges[self._size]
    self._out_edges[self._size] = idx

  def out_edges(self, source: int):
    """Generate all outgoing edges."""
    for idx, (target, attrs) in enumerate(self._out_edges[:self._size]):
      yield Edge(source, target, attrs, idx)

  def __len__(self):
    """Return the number of edges in this adjacency list."""
    return self._size

  def _index(self, target: int, idx: int = None):
    """Return index of an / the edge pointing at vertex `target`.

    Raise a ValueError if there is no such edge.

    If `idx` is None, return index of the first edge pointing at `target`.
    Otherwise, return current index of the edge that originally sat at `idx`.
    """
    if idx is None:
      for idx in range(self._size):
        if self._out_edges[idx][0] == target:
          return idx
    else:
      assert 0 <= idx < len(self._out_edges)
      while idx >= self._size:
        idx, self._out_edges[idx] = self._out_edges[idx], None
      if target is None or self._out_edges[idx][0] == target:
        return idx
    raise ValueError('vertex {} is not in adjacency list'.format(target))


class AdjacencyLists(Graph):

  def __init__(self, vertex_count, make_list=None):
    """Initialize the graph with the given number of vertices."""
    super().__init__(vertex_count)
    self._make_list = make_list if make_list is not None else AdjacencyList
    self._adj_lists = [self._make_list() for _ in range(vertex_count)]

  # --------------------------------------------------------------------------

  def add_edge(self, source: int, target: int, attrs=None, **kwargs):
    """Add a directed edge from source to target with given attributes.

    Returns: edge handle that can be used in `remove` and 'get' methods.
    """
    attrs = self._get_attrs(attrs, kwargs)
    return self._adj_lists[source].add(target, attrs)

  def get_edge(self, source: int, target: int, handle=None):
    """Retrieve a directed edge from source to target.

    Returns: tuple[edge attrs, edge handle]
    """
    return self._adj_lists[source].get(source, target, handle)

  def remove_edge(self, source: int, target: int, handle=None):
    """Remove a directed edge from source to target."""
    self._adj_lists[source].remove(target, handle)

  # --------------------------------------------------------------------------

  def out_edges(self, source: int):
    """Generate all outgoing edges from a given source vertex."""
    # assert 0 <= source < self.vertex_count()
    yield from self._adj_lists[source].out_edges(source)

  # --------------------------------------------------------------------------

  def out_degree(self, source: int) -> int:
    """Get the out-degree of a given source vertex."""
    # assert 0 <= source < self.vertex_count()
    return len(self._adj_lists[source])


class Clique(Graph):

  def __init__(self, vertex_count, get_attrs=None):
    """Initialize the clique with the given number of rows and columns."""
    super().__init__(vertex_count)
    # Returns attributes of the edge between vertices u and v.
    self.get_attrs = (get_attrs if get_attrs is not None else
                      lambda u, v: Edge.attrs)

  # --------------------------------------------------------------------------

  # TODO get_edge()

  # --------------------------------------------------------------------------

  def out_edges(self, source: int):
    """Generate all outgoing edges from a given source vertex."""
    for target in self.vertices():
      if source != target:
        yield Edge(source, target, self.get_attrs(source, target))

  def in_edges(self, target: int):
    """Generate all incoming edges to a given target vertex."""
    for source in self.vertices():
      if source != target:
        yield Edge(source, target, self.get_attrs(source, target))

  # --------------------------------------------------------------------------

  def out_degree(self, source: int) -> int:
    """Get the out-degree of a given source vertex."""
    return self._vertex_count - 1

  def out_degrees(self) -> list[int]:
    """Get the list of out-degrees of all vertices in the graph."""
    return [self._vertex_count - 1 for source in self.vertices()]

  def in_degree(self, target: int) -> int:
    """Get the in-degree of a given target vertex."""
    return self._vertex_count - 1

  def in_degrees(self) -> list[int]:
    """Get the list of in-degrees of all vertices in the graph."""
    return [self._vertex_count - 1 for source in self.vertices()]

  # --------------------------------------------------------------------------

  def edge_count(self) -> int:
    """Get the number of edges in the graph."""
    raise self._vertex_count * (self._vertex_count - 1)


class Grid(Graph):

  class Type:
    k4Way = 1  # default
    k8Way = 2
    kKnight = 3

  def __init__(self, rows=0, cols=0, grid_type=None, get_attrs=None):
    """Initialize the grid with the given number of rows and columns."""
    super().__init__(rows * cols)
    self.rows = rows
    self.cols = cols
    # Returns attributes of the edge between cells (r1,c1) and (r2,c2):
    self.get_attrs = (get_attrs if get_attrs is not None else
                      lambda r1, c1, r2, c2: Edge.attrs)
    # Implementation details:
    grid_type = Grid.Type.k4Way if grid_type is None else grid_type
    match grid_type:
      case Grid.Type.k4Way:
        self._neighborhood = [(1, 0), (0, 1), (-1, 0), (0, -1)]
      case Grid.Type.k8Way:
        self._neighborhood = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        self._neighborhood += [(1, 1), (1, -1), (-1, 1), (-1, -1)]
      case Grid.Type.kKnight:
        self._neighborhood = [(-2, -1), (-2, 1), (2, -1), (2, 1)]
        self._neighborhood += [(-1, -2), (1, -2), (-1, 2), (1, 2)]

  # --------------------------------------------------------------------------

  # TODO get_edge()

  # --------------------------------------------------------------------------

  def out_edges(self, source: int):
    """Generate all outgoing edges from a given source vertex."""
    # assert 0 <= source < self.vertex_count()
    sr, sc = self.idx2coor(source)
    for tr, tc in self._get_neighbor_cells(sr, sc):
      attrs = self.get_attrs(sr, sc, tr, tc)
      if attrs is not None:
        yield Edge(source, self.coor2idx(tr, tc), attrs)

  def in_edges(self, target: int):
    """Generate all incoming edges to a given target vertex."""
    # assert 0 <= target < self.vertex_count()
    tr, tc = self.idx2coor(target)
    for sr, sc in self._get_neighbor_cells(tr, tc):
      attrs = self.get_attrs(sr, sc, tr, tc)
      if attrs is not None:
        yield Edge(self.coor2idx(sr, sc), target, attrs)

  def _get_neighbor_cells(self, r1: int, c1: int) -> list[tuple[int, int]]:
    """Generate the valid neighboring cells for a given grid cell."""
    for dr, dc in self._neighborhood:
      r2, c2 = r1 + dr, c1 + dc
      if (0 <= r2 < self.rows) and (0 <= c2 < self.cols):
        yield r2, c2

  # --------------------------------------------------------------------------

  def coor2idx(self, r: int, c: int) -> int:
    """Convert a pair of grid coordinates to a linear index."""
    return r * self.cols + c

  def idx2coor(self, idx: int) -> tuple[int, int]:
    """Convert a linear index to a pair of grid coordinates."""
    return (idx // self.cols, idx % self.cols)


class VertexMap:
  """A utility class to map vertex labels to int indices and vice versa."""

  def __init__(self):
    self.l2i = {}  # label to index map
    self.i2l = []  # index to label map
    self._vertex_count = 0

  def add_vertex(self, label):
    """
    Add a vertex with the given label to the map.
    If label already exists, return its index.
    """
    return self.get_index(label)

  def get_index(self, label) -> int:
    """
    Get the index corresponding to the given label.
    If label doesn't exist, create an entry for it.
    """
    idx = self.l2i.setdefault(label, self.vertex_count())
    if idx == self._vertex_count:
      self.i2l.append(label)
      self._vertex_count += 1
    return idx

  def get_label(self, v: int):
    """Get the label corresponding to the given index."""
    assert 0 <= v < self._vertex_count
    return self.i2l[v]

  def vertex_count(self) -> int:
    """Get the number of vertices in the map."""
    return self._vertex_count


# ----------------------------------------------------------------------------
# Breath-First Search (BFS)
# ----------------------------------------------------------------------------

import collections
import math


class BFS:
  """Breath-First Search (BFS)"""

  class Observer:

    def init(self, traversal):
      self.traversal = traversal
      self.graph = traversal.graph

    def start_traversal(self, sources: list[int]):
      ...

    def finish_traversal(self):
      ...

    def stop_traversal(self):
      ...

    def enter_vertex(self, u: int, cost_u):
      ...

    def exit_vertex(self, u: int):
      ...

    def traverse_tree_edge(self, edge: Edge, target_cost):
      ...

    def visit_edge(self, edge: Edge, target_cost):
      ...


  class StopTraversal(Exception):
    ...

  class SkipVertex(Exception):
    ...

  class VStatus:
    UNDISCOVERED = 1
    ENQUEUED = 2
    EXITED = 3

  def __init__(self, graph, observer=None, get_cost=None, make_queue=None):
    # Traversal state:
    self.statuses = [self.VStatus.UNDISCOVERED] * graph.vertex_count()
    self.costs = [math.inf] * graph.vertex_count()
    self.queue = None
    self.stopped = False
    # Traversal parameters:
    self.graph = graph
    self.observer = observer if observer is not None else self.Observer()
    self.get_cost = get_cost if get_cost is not None else self.cost
    self.make_queue = make_queue if make_queue is not None else self.Queue
    self.observer.init(self)

  # -- Cost & Queue Definitions ----------------------------------------------

  @staticmethod
  def cost(cost_u, edge_uv: Edge):
    return cost_u + 1

  class Queue:

    def __init__(self):
      self._queue = collections.deque()

    def put(self, edge: Edge, target_cost):
      self._queue.append((edge, target_cost))

    def pop(self):
      # assert len(self._queue) > 0
      return self._queue.popleft()

    def __len__(self):
      return len(self._queue)

  # -- Traversal Configuration -----------------------------------------------

  # If you are getting TLE, consider inlining the config methods, especially
  # `_visit_edge` and `_enqueue`.

  def _enter_vertex(self, u: int, cost_u):
    # assert self.statuses[v] == self.VStatus.ENQUEUED
    self.costs[u] = cost_u

  def _visit_edge(self, edge: Edge, target_cost):
    if self.statuses[edge.target] == self.VStatus.UNDISCOVERED:
      self._enqueue(edge, target_cost)

  def _enqueue(self, edge: Edge, target_cost):
    # UNDISCOVERED -> ENQUEUED
    self.statuses[edge.target] = self.VStatus.ENQUEUED
    self.queue.put(edge, target_cost)

  def _exit_vertex(self, u: int):
    # ENQUEUED -> EXITED
    self.statuses[u] = self.VStatus.EXITED

  # -- Traversal -------------------------------------------------------------

  def run(self, sources: list[int], source_cost=0):
    if isinstance(sources, int):
      sources = [sources]
    self.queue = self.make_queue()
    self.stopped = False
    for u in sources:
      self._visit_edge(Edge(source=-1, target=u), source_cost)
    if not self.queue:
      return
    try:
      self.observer.start_traversal(sources)
      while self.queue:
        try:
          in_edge, cost_u = self.queue.pop()
          u = in_edge.target
          if in_edge.source >= 0:
            self.observer.traverse_tree_edge(in_edge, cost_u)
          self._enter_vertex(u, cost_u)
          self.observer.enter_vertex(u, cost_u)
          for out_edge in self.graph.out_edges(u):
            cost_v = self.get_cost(cost_u, out_edge)
            self.observer.visit_edge(out_edge, cost_v)
            self._visit_edge(out_edge, cost_v)
          self.observer.exit_vertex(u)
          self._exit_vertex(u)
        except self.SkipVertex:
          ...
    except self.StopTraversal:
      self.observer.stop_traversal()
      self.stopped = True
    else:
      self.observer.finish_traversal()


# ----------------------------------------------------------------------------
# BFS Variants
# ----------------------------------------------------------------------------


class TopologicalBFS(BFS):

  def __init__(self, graph, *args, **kwargs):
    super().__init__(graph, *args, **kwargs)
    self.in_degs = graph.in_degrees()

  def _visit_edge(self, edge: Edge, target_cost):
    self.in_degs[edge.target] -= 1
    if self.in_degs[edge.target] <= 0:
      self._enqueue(edge, target_cost)

  def run(self):
    super().run([u for u in self.graph.vertices() if self.in_degs[u] == 0])


class RestrictedBFS(BFS):

  class VStatus:
    UNDISCOVERED = 1
    DISCOVERED = 2
    ENQUEUED = 3
    EXITED = 4

  def __init__(self, graph, *args, **kwargs):
    super().__init__(graph, *args, **kwargs)
    self.open = [True] * graph.vertex_count()
    self.in_edges = [None] * graph.vertex_count()

  def _visit_edge(self, edge: Edge, target_cost):
    if self.statuses[edge.target] == self.VStatus.UNDISCOVERED:
      if self.open[edge.target]:
        # UNDISCOVERED -> ENQUEUED
        self._enqueue(edge, target_cost)
      else:
        # UNDISCOVERED -> DISCOVERED
        self.statuses[edge.target] = self.VStatus.DISCOVERED
    if self.statuses[edge.target] == self.VStatus.DISCOVERED:
      # assert not self.open[edge.target]
      self.in_edges[edge.target] = edge 
      self.costs[edge.target] = target_cost

  def unlock(self, u: int):
    self.open[u] = True
    if self.statuses[u] == self.VStatus.DISCOVERED:
      # DISCOVERED -> ENQUEUED
      self._enqueue(self.in_edges[u], self.costs[u])


class MultiEntryBFS(BFS):

  def __init__(self, graph, max_entry_count=1, *args, **kwargs):
    super().__init__(graph, *args, **kwargs)
    self.max_entry_count = max_entry_count
    self.entry_counts = [0] * graph.vertex_count()

  def _enter_vertex(self, u: int, cost_u):
    # assert self.costs[u] <= cost_u
    # TODO: multiple entries with the same cost -> add a config param
    if self.statuses[u] == self.VStatus.EXITED or self.costs[u] == cost_u:
      raise self.SkipVertex
    self.costs[u] = cost_u
    self.entry_counts[u] += 1

  def _visit_edge(self, edge: Edge, target_cost):
    if self.statuses[edge.target] != self.VStatus.EXITED:
      self._enqueue(edge, target_cost)

  def _exit_vertex(self, u: int):
    if self.entry_counts[u] >= self.max_entry_count:
      self.statuses[u] = self.VStatus.EXITED


# ----------------------------------------------------------------------------
# BFS Observers
# ----------------------------------------------------------------------------


class ToTarget(BFS.Observer):

  def __init__(self, target: int):
    self.target = target

  def init(self, traversal):
    super().init(traversal)
    if self.target < 0:
      self.target += self.graph.vertex_count()
    assert 0 <= self.target < self.graph.vertex_count()

  def enter_vertex(self, u: int, cost_u):
    if u == self.target:
      raise self.traversal.StopTraversal


class ToTargets(BFS.Observer):

  def __init__(self, targets: list[int]):
    self.targets = targets

  def init(self, traversal):
    super().init(traversal)
    self.reached_count = 0
    for i in range(len(self.targets)):
      if self.targets[i] < 0:
        self.targets[i] += self.graph.vertex_count()
    self.targets = {u: 1 for u in self.targets}

  def enter_vertex(self, u: int, cost_u):
    if u in self.targets:
      self.reached_count += 1
    if self.reached_count == len(self.targets):
      raise self.traversal.StopTraversal


class ToCost(BFS.Observer):

  def __init__(self, target_cost):
    self.target_cost = target_cost

  def enter_vertex(self, u: int, cost_u):
    if cost_u > self.target_cost:
      raise self.traversal.SkipVertex


class InEdges(BFS.Observer):

  def init(self, traversal):
    super().init(traversal)
    self.in_edges = [None] * self.graph.vertex_count()

  def traverse_tree_edge(self, edge: Edge, target_cost):
    self.in_edges[edge.target] = edge


# ----------------------------------------------------------------------------
# BFS-based Algorithms
# ----------------------------------------------------------------------------


def find_cc(graph):

  class ConnectedComponents(BFS.Observer):
  
    def __init__(self):
      self.count = 0
      self.vertex2comp = [-1] * graph.vertex_count()
      self.comp2vertices = []
  
    def start_traversal(self, sources):
      self.count += 1
      self.comp2vertices.append([])
  
    def enter_vertex(self, u, cost_u):
      self.vertex2comp[u] = self.count - 1
      self.comp2vertices[self.count - 1].append(u)
  
  cc = ConnectedComponents()
  bfs = BFS(graph, cc)
  for v in graph.vertices():
    bfs.run(v)
  return cc


def find_layers(graph):

  class Layers(BFS.Observer):

    def __init__(self):
      self.vertex2layer = [-1] * graph.vertex_count()
      self.layer2vertices = collections.defaultdict(list)

    def start_traversal(self, sources):
      for u in sources:
        self.vertex2layer[u] = 0

    def enter_vertex(self, u, cost_u):
      self.layer2vertices[self.vertex2layer[u]].append(u)

    def visit_edge(self, edge: Edge, target_cost):
      self.vertex2layer[edge.target] = max(self.vertex2layer[edge.target],
                                           self.vertex2layer[edge.source] + 1)

  layers = Layers()
  TopologicalBFS(graph, layers).run()
  return layers


def sort_topologically(graph, bfs_cls=TopologicalBFS):

  class Order(BFS.Observer):

    def __init__(self):
      self.vertices = []

    def enter_vertex(self, u, cost_u):
      self.vertices.append(u)

  obs = Order()
  bfs_cls(graph, obs).run()
  return obs.vertices


# ----------------------------------------------------------------------------
# MinCost-First Search (MCFS)
# ----------------------------------------------------------------------------

import sortedcontainers


class MCFS(BFS):
  """MinCost-First Search (MCFS)"""

  @staticmethod
  def cost(cost_u, edge_uv: Edge):
    return cost_u + edge_uv.attrs

  class Queue:

    def __init__(self):
      self._items = sortedcontainers.SortedSet()

    def put(self, edge, target_cost):
      self._items.add(self._Item(target_cost, edge))

    def pop(self):
      # assert len(self._items) > 1
      item = self._items.pop(0)
      return item.edge, item.target_cost

    def __len__(self):
      return len(self._items)

    @dataclass
    class _Item:
      target_cost: Any
      edge: Any

      def __lt__(self, other):
        return self.target_cost < other.target_cost

      def __hash__(self):
        return hash(self.target_cost)

  def _enter_vertex(self, u: int, cost_u):
    if self.statuses[u] == self.VStatus.EXITED:
      raise self.SkipVertex
    self.costs[u] = cost_u

  def _visit_edge(self, edge, target_cost):
    if self.costs[edge.target] > target_cost:
      self.costs[edge.target] = target_cost
      self._enqueue(edge, target_cost)


# ----------------------------------------------------------------------------
# MCFS Variants
# ----------------------------------------------------------------------------


class BinaryMCFS(MCFS):
  """Works for graphs where each edge's cost is either 0 or 1."""

  class Queue(BFS.Queue):

    def put(self, edge, target_cost):
      if self._queue and self._queue[-1][1] <= target_cost:
        self._queue.append((edge, target_cost))
      else:
        self._queue.appendleft((edge, target_cost))


class BoundedMCFS(MCFS):
  """Works for graphs where max vertex's cost is ~ O(graph.edge_count())."""

  class Queue:

    def __init__(self):
      self._queue = []
      self._size = 0
      self._cost = 0

    def put(self, edge: Edge, target_cost):
      # assert target_cost >= self._cost
      queue_len = len(self._queue)
      if target_cost >= queue_len:
        self._queue.extend([[] for _ in range(target_cost - queue_len + 1)])
      self._queue[target_cost].append(edge)
      self._size += 1

    def pop(self):
      # assert self._size > 0
      while not self._queue[self._cost]:
        self._cost += 1
      edge = self._queue[self._cost].pop()
      self._size -= 1
      return edge, self._cost

    def __len__(self):
      return self._size


class MultiEntryMCFS(MultiEntryBFS):

  cost = MCFS.cost

  Queue = MCFS.Queue


# ----------------------------------------------------------------------------
# MCFS-based Algorithms
# ----------------------------------------------------------------------------

# TODO: implement


# ----------------------------------------------------------------------------
# Depth-First Search
# ----------------------------------------------------------------------------


class DFS:
  """Depth-first Search (DFS)"""

  class Observer:

    def init(self, traversal):
      self.traversal = traversal
      self.graph = traversal.graph

    # -- Event Handlers ------------------------------------------------------

    def start_traversal(self, source: int):
      ...

    def finish_traversal(self):
      ...

    def stop_traversal(self):
      ...

    def enter_vertex(self, u: int):
      ...

    def exit_vertex(self, u: int):
      ...

    def traverse_tree_edge(self, edge: Edge):
      ...

    def retrace_tree_edge(self, edge: Edge):
      ...

    def visit_backward_edge(self, edge: Edge):
      # Hint: Check if edge.target == self.traversal.parents[edge.source].
      ...

    def visit_forward_edge(self, edge: Edge):
      ...

    def visit_cross_edge(self, edge: Edge):
      ...

  class StopTraversal(Exception):
    ...

  class VStatus:
    UNDISCOVERED = 1
    ENTERED = 2
    EXITED = 3

  def __init__(self, graph, observer=None):
    # Traversal state:
    self.statuses = [self.VStatus.UNDISCOVERED] * graph.vertex_count()
    self.entry_times = [0] * graph.vertex_count()
    self.parents = [-1] * graph.vertex_count()
    self.time = 0
    self.stack = None
    self.stopped = False
    self._out_edges = [graph.out_edges(v) for v in graph.vertices()]
    # Traversal parameters:
    self.graph = graph
    self.observer = observer if observer is not None else self.Observer()
    self.observer.init(self)

  # -- Traversal Configuration -----------------------------------------------

  def _enter_vertex(self, v: int):
    # UNDISCOVERED -> ENTERED
    self.statuses[v] = self.VStatus.ENTERED
    self.time += 1
    self.entry_times[v] = self.time

  def _exit_vertex(self, v: int):
    # ENTERED -> EXITED
    self.statuses[v] = self.VStatus.EXITED

  # -- Traversal -------------------------------------------------------------

  def run(self, source: int):
    if self.statuses[source] != self.VStatus.UNDISCOVERED:
      return
    stack = [Edge(source=-1, target=source)]
    self.stopped = False
    try:
      self.observer.start_traversal(source)
      while stack:
        edge = stack[-1]
        p = edge.source  # previous vertex
        u = edge.target
        match self.statuses[u]:
          case self.VStatus.UNDISCOVERED:
            self.parents[u] = p
            if p >= 0:
              self.observer.traverse_tree_edge(edge)
            self._enter_vertex(u)
            self.observer.enter_vertex(u)
          case self.VStatus.EXITED:
            stack.pop()
            if self.entry_times[u] > self.entry_times[p]:
              self.observer.visit_forward_edge(edge)
            else:
              self.observer.visit_cross_edge(edge)
          case self.VStatus.ENTERED:
            if p >= 0 and self.entry_times[u] < self.entry_times[p]:
              stack.pop()
              self.observer.visit_backward_edge(edge)
            else:
              try:
                stack.append(next(self._out_edges[u]))
              except StopIteration:
                self.observer.exit_vertex(u)
                self._exit_vertex(u)
                stack.pop()
                if p >= 0:
                  self.observer.retrace_tree_edge(edge)
    except self.StopTraversal:
      self.stopped = True
      self.observer.stop_traversal()
    else:
      self.observer.finish_traversal()


# ----------------------------------------------------------------------------
# DFS-based Algorithms
# ----------------------------------------------------------------------------


def find_scc(graph):

  class Pass1(DFS.Observer):

    def __init__(self):
      self.order = []

    def exit_vertex(self, u):
      self.order.append(u)

  pass1 = Pass1()
  dfs1 = DFS(graph, pass1)
  for v in graph.vertices():
    dfs1.run(v)

  class StronglyConnectedComponents(DFS.Observer):

    def __init__(self):
      self.count = 0
      self.vertex2comp = [-1] * graph.vertex_count()
      self.comp2vertices = []

    def start_traversal(self, source):
      self.count += 1
      self.comp2vertices.append([])

    def enter_vertex(self, u):
      self.vertex2comp[u] = self.count - 1
      self.comp2vertices[self.count - 1].append(u)

  scc = StronglyConnectedComponents()
  dfs2 = DFS(transposed(graph), scc)
  for v in reversed(pass1.order):
    dfs2.run(v)
  return scc


def build_condensation_graph(graph, scc=None):
  if scc is None:
    scc = find_scc(graph)
  edges = set()
  for c in range(scc.count):
    for u in scc.comp2vertices[c]:
      for v, _ in graph.out_edges(u):
        if scc.vertex2comp[v] == c: continue
        edges.add((c, scc.vertex2comp[v]))
  cond_graph = AdjacencyLists(scc.count)
  cond_graph.add_edges(edges)
  return cond_graph


def find_bridges_and_cutpoints(graph):

  class Finder(DFS.Observer):

    def __init__(self):
      self.low = [graph.vertex_count() + 1] * graph.vertex_count()
      self.bridges = []
      self.is_cutpoint = [False] * graph.vertex_count()

    def start_traversal(self, source):
      self.root = source

    def finish_traversal(self):
      if self.traversal.parents.count(self.root) > 1:
        self.is_cutpoint[self.root] = True

    def enter_vertex(self, u):
      self.low[u] = self.traversal.entry_times[u]

    def visit_backward_edge(self, edge: Edge):
      u, v = edge.source, edge.target
      if v == self.traversal.parents[u]: return
      self.low[u] = min(self.low[u], self.traversal.entry_times[v])

    def retrace_tree_edge(self, edge: Edge):
      u, v = edge.source, edge.target
      self.low[u] = min(self.low[u], self.low[v])
      if self.low[v] >= self.traversal.entry_times[v]:
        self.bridges.append(edge)
      if self.low[v] >= self.traversal.entry_times[u] and u != self.root:
        self.is_cutpoint[u] = True

  finder = Finder()
  dfs = DFS(graph, finder)
  for v in graph.vertices():
    dfs.run(v)

  return finder.bridges, finder.is_cutpoint
12798