"""simple docstring"""


def 			__UpperCAmelCase    (	lowercase						):







  """simple docstring"""
  return [
      {
          0: [1, 2],
          1: [0, 2],
          2: [0, 1, 3, 5],
          3: [2, 4],
          4: [3],
          5: [2, 6, 8],
          6: [5, 7],
          7: [6, 8],
          8: [5, 7],
      },
      {
          0: [6],
          1: [9],
          2: [4, 5],
          3: [4],
          4: [2, 3],
          5: [2],
          6: [0, 7],
          7: [6],
          8: [],
          9: [1],
      },
      {
          0: [4],
          1: [6],
          2: [],
          3: [5, 6, 7],
          4: [0, 6],
          5: [3, 8, 9],
          6: [1, 3, 4, 7],
          7: [3, 6, 8, 9],
          8: [5, 7],
          9: [5, 7],
      },
      {
          0: [1, 3],
          1: [0, 2, 4],
          2: [1, 3, 4],
          3: [0, 2, 4],
          4: [1, 2, 3],
      },
  ][index]






def 			__UpperCAmelCase    (	lowercase						):







  """simple docstring"""
  _UpperCAmelCase         =					0
  _UpperCAmelCase         =					len(lowercase						)  # No of vertices in graph
  _UpperCAmelCase         =					[0] * n
  _UpperCAmelCase         =					[False] * n

  def dfs(lowercase      ,lowercase      ,lowercase      ,lowercase						):
    _UpperCAmelCase         =					True
    _UpperCAmelCase         =					id_
    id_ += 1
    for to in graph[at]:
      if to == parent:
        pass
      elif not visited[to]:
        dfs(lowercase      ,lowercase      ,lowercase      ,id_						)
        _UpperCAmelCase         =					min(low[at]      ,low[to]						)
        if id_ <= low[to]:
          bridges.append((at, to) if at < to else (to, at)						)
      else:
        # This edge is a back edge and cannot be a bridge
        _UpperCAmelCase         =					min(low[at]      ,low[to]						)

  _UpperCAmelCase         =					[]
  for i in range(lowercase						):
    if not visited[i]:
      dfs(lowercase      ,-1      ,lowercase      ,id_						)
  return bridges


if __name__ == "__main__":
    import doctest

    doctest.testmod()

"""simple docstring"""


from __future__ import annotations

from collections import Counter
from random import random


class 				a :


    def __init__(    self		:     Union[str, Any]    ):
      _UpperCAmelCase         =					{}


    def    lowerCAmelCase_     (    self		:     Optional[int]      , __lowerCAmelCase		:     str    ):
      _UpperCAmelCase         =					{}


    def    lowerCAmelCase_     (    self		:     str      , __lowerCAmelCase		:     str      , __lowerCAmelCase		:     str      , __lowerCAmelCase		:     float    ):
      if nodea not in self.connections:
        self.add_node(__lowerCAmelCase    )
      if nodea not in self.connections:
        self.add_node(__lowerCAmelCase    )
      _UpperCAmelCase         =					probability


    def    lowerCAmelCase_     (    self		:     Optional[Any]    ):
      return list(self.connections    )


    def    lowerCAmelCase_     (    self		:     List[Any]      , __lowerCAmelCase		:     str    ):
      _UpperCAmelCase         =					0
      _UpperCAmelCase         =					random()

      for dest in self.connections[node]:
        current_probability += self.connections[node][dest]
        if current_probability > random_value:
          return dest
      return ""






def 			__UpperCAmelCase    (	lowercase      ,lowercase      ,lowercase						):







  """simple docstring"""
  _UpperCAmelCase         =					MarkovChainGraphUndirectedUnweighted()

  for nodea, nodea, probability in transitions:
    graph.add_transition_probability(lowercase      ,lowercase      ,lowercase						)

  _UpperCAmelCase         =					Counter(graph.get_nodes()						)
  _UpperCAmelCase         =					start

  for _ in range(lowercase						):
    _UpperCAmelCase         =					graph.transition(lowercase						)
    visited[node] += 1

  return visited


if __name__ == "__main__":
    import doctest

    doctest.testmod()
