


from collections import deque
def 							UpperCAmelCase_   (				__snake_case		)	->     Any:







 """simple docstring"""


 return input(lowercase_		).strip().split(''' '''		)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     dict[int, list[int]]:







 """simple docstring"""


 _lowercase				 ={}
 for i in range(lowercase_		):
  _lowercase				 =[]

 for e in range(lowercase_		):
  _lowercase ,       _lowercase				 =(int(lowercase_		) for i in _input(F"Edge {e + 1}: <node1> <node2> "		))
  graph[x].append(lowercase_		)
 return graph
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     dict[int, list[int]]:







 """simple docstring"""


 _lowercase				 ={}
 for i in range(lowercase_		):
  _lowercase				 =[]

 for e in range(lowercase_		):
  _lowercase ,       _lowercase				 =(int(lowercase_		) for i in _input(F"Edge {e + 1}: <node1> <node2> "		))
  graph[x].append(lowercase_		)
  graph[y].append(lowercase_		)
 return graph
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     dict[int, list[tuple[int, int]]]:







 """simple docstring"""


 _lowercase				 ={}
 for i in range(lowercase_		):
  _lowercase				 =[]

 for e in range(lowercase_		):
  _lowercase ,       _lowercase ,       _lowercase				 =(int(lowercase_		) for i in _input(F"Edge {e + 1}: <node1> <node2> <weight> "		))
  graph[x].append((y, w)		)
  graph[y].append((x, w)		)
 return graph


if __name__ == "__main__":
  UpperCAmelCase__      ,UpperCAmelCase__        =				(int(i) for i in _input('''Number of nodes and edges: '''))

  UpperCAmelCase__        =				int(
      _input(
          '''Press 1 or 2 or 3 \n'''
          '''1. Unweighted directed \n'''
          '''2. Unweighted undirected \n'''
          '''3. Weighted undirected \n'''
      )[0]
  )

  UpperCAmelCase__        =				{
      1: initialize_unweighted_directed_graph,
      2: initialize_unweighted_undirected_graph,
      3: initialize_weighted_undirected_graph,
  }[graph_choice](n, m)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     Any:







 """simple docstring"""


 _lowercase ,       _lowercase				 ={s}, [s]
 print(lowercase_		)
 while _s:
  _lowercase				 =0
  for i in g[_s[-1]]:
   if i not in vis:
    _s.append(lowercase_		)
    vis.add(lowercase_		)
    _lowercase				 =1
    print(lowercase_		)
    break
  if not flag:
   _s.pop()
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     Tuple:







 """simple docstring"""


 _lowercase ,       _lowercase				 ={s}, deque([s]		)
 print(lowercase_		)
 while q:
  _lowercase				 =q.popleft()
  for v in g[u]:
   if v not in vis:
    vis.add(lowercase_		)
    q.append(lowercase_		)
    print(lowercase_		)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     Union[str, Any]:







 """simple docstring"""


 _lowercase ,       _lowercase ,       _lowercase				 ={s: 0}, set(), {s: 0}
 while True:
  if len(lowercase_		) == len(lowercase_		) - 1:
   break
  _lowercase				 =100000
  for i in dist:
   if i not in known and dist[i] < mini:
    _lowercase				 =dist[i]
    _lowercase				 =i
  known.add(lowercase_		)
  for v in g[u]:
   if v[0] not in known and dist[u] + v[1] < dist.get(v[0]	,		100000		):
    _lowercase				 =dist[u] + v[1]
    _lowercase				 =u
 for i in dist:
  if i != s:
   print(dist[i]		)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case=None	,		__snake_case=None		)	->     Tuple:







 """simple docstring"""


 if q is None:
  _lowercase				 =[1]
 if ind is None:
  _lowercase				 =[0] * (len(lowercase_		) + 1)  # SInce oth Index is ignored
  for u in g:
   for v in g[u]:
    ind[v] += 1
  _lowercase				 =deque()
  for i in g:
   if ind[i] == 0:
    q.append(lowercase_		)
 if len(lowercase_		) == 0:
  return
 _lowercase				 =q.popleft()
 print(lowercase_		)
 for w in g[v]:
  ind[w] -= 1
  if ind[w] == 0:
   q.append(lowercase_		)
 topo(lowercase_	,		lowercase_	,		lowercase_		)
def 							UpperCAmelCase_   (				)	->     int:







 """simple docstring"""


 _lowercase				 =input().strip()
 _lowercase				 =[]
 for _ in range(lowercase_		):
  a.append(map(lowercase_	,		input().strip().split()		)		)
 return a, n
def 							UpperCAmelCase_   (				__snake_case		)	->     List[Any]:







 """simple docstring"""


 ((_lowercase) ,       (_lowercase))				 =a_and_n
 _lowercase				 =list(lowercase_		)
 _lowercase				 =[[0] * n for i in range(lowercase_		)]
 for k in range(lowercase_		):
  for i in range(lowercase_		):
   for j in range(lowercase_		):
    if dist[i][j] > dist[i][k] + dist[k][j]:
     _lowercase				 =dist[i][k] + dist[k][j]
     _lowercase				 =k
 print(lowercase_		)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     Dict:







 """simple docstring"""


 _lowercase ,       _lowercase ,       _lowercase				 ={s: 0}, set(), {s: 0}
 while True:
  if len(lowercase_		) == len(lowercase_		) - 1:
   break
  _lowercase				 =100000
  for i in dist:
   if i not in known and dist[i] < mini:
    _lowercase				 =dist[i]
    _lowercase				 =i
  known.add(lowercase_		)
  for v in g[u]:
   if v[0] not in known and v[1] < dist.get(v[0]	,		100000		):
    _lowercase				 =v[1]
    _lowercase				 =u
 return dist
def 							UpperCAmelCase_   (				)	->     Dict:







 """simple docstring"""


 _lowercase ,       _lowercase				 =map(lowercase_	,		input().split(''' '''		)		)
 _lowercase				 =[]
 for _ in range(lowercase_		):
  edges.append(map(lowercase_	,		input().split(''' '''		)		)		)
 return edges, n
def 							UpperCAmelCase_   (				__snake_case		)	->     Tuple:







 """simple docstring"""


 ((_lowercase) ,       (_lowercase))				 =e_and_n
 e.sort(reverse=lowercase_	,		key=lambda __snake_case		: x[2]		)
 _lowercase				 =[{i} for i in range(1	,		n + 1		)]
 while True:
  if len(lowercase_		) == 1:
   break
  print(lowercase_		)
  _lowercase				 =e.pop()
  for i in range(len(lowercase_		)		):
   if x[0] in s[i]:
    break
  for j in range(len(lowercase_		)		):
   if x[1] in s[j]:
    if i == j:
     break
    s[j].update(s[i]		)
    s.pop(lowercase_		)
    break



def 							UpperCAmelCase_   (				__snake_case		)	->     List[str]:







 """simple docstring"""


 _lowercase				 =[]
 for node in graph:
  if not graph[node]:
   isolated.append(lowercase_		)
 return isolated




import unittest

from diffusers import __version__
from diffusers.utils import deprecate







class 					__lowerCamelCase							(      unittest.TestCase      ):
      lowerCamelCase_      : Dict  			=   '.'.join([str(int(__version__.split('.'      )[0]      ) + 1      )] + __version__.split('.'      )[1:]      )
      lowerCamelCase_      : int  			=   '0.0.1'







      def       lowerCAmelCase_       (	self  )		->			Optional[int]:
        snake_case_					= {"""deprecated_arg""": 4}

        with self.assertWarns(lowerCamelCase  ) as warning:
          snake_case_					= deprecate("""deprecated_arg"""				,    self.higher_version				,    """message"""				,    take_from=lowerCamelCase  )

        assert output == 4
        assert (
            str(warning.warning  )
            == f'''The `deprecated_arg` argument is deprecated and will be removed in version {self.higher_version}.'''
            " message"
        )







      def       lowerCAmelCase_       (	self  )		->			List[Any]:
        snake_case_					= {"""deprecated_arg""": 4}

        with self.assertWarns(lowerCamelCase  ) as warning:
          snake_case_					= deprecate(("""deprecated_arg""", self.higher_version, """message""")				,    take_from=lowerCamelCase  )

        assert output == 4
        assert (
            str(warning.warning  )
            == f'''The `deprecated_arg` argument is deprecated and will be removed in version {self.higher_version}.'''
            " message"
        )







      def       lowerCAmelCase_       (	self  )		->			int:
        snake_case_					= {"""deprecated_arg_1""": 4, """deprecated_arg_2""": 8}
        with self.assertWarns(lowerCamelCase  ) as warning:
          snake_case_		,							snake_case_					= deprecate(
              ("""deprecated_arg_1""", self.higher_version, """Hey""")				,    ("""deprecated_arg_2""", self.higher_version, """Hey""")				,    take_from=lowerCamelCase				,    )
        assert output_a == 4
        assert output_a == 8
        assert (
            str(warning.warnings[0].message  )
            == "The `deprecated_arg_1` argument is deprecated and will be removed in version"
            f''' {self.higher_version}. Hey'''
        )
        assert (
            str(warning.warnings[1].message  )
            == "The `deprecated_arg_2` argument is deprecated and will be removed in version"
            f''' {self.higher_version}. Hey'''
        )







      def       lowerCAmelCase_       (	self  )		->			Any:
        snake_case_					= {"""deprecated_arg""": 4}

        with self.assertRaises(lowerCamelCase  ) as error:
          deprecate(("""wrong_arg""", self.higher_version, """message""")				,    take_from=lowerCamelCase  )

        assert "test_deprecate_function_incorrect_arg in" in str(error.exception  )
        assert "line" in str(error.exception  )
        assert "got an unexpected keyword argument `deprecated_arg`" in str(error.exception  )







      def       lowerCAmelCase_       (	self  )		->			Optional[Any]:
        with self.assertWarns(lowerCamelCase  ) as warning:
          deprecate(("""deprecated_arg""", self.higher_version, """message""")  )

        assert (
            str(warning.warning  )
            == f'''`deprecated_arg` is deprecated and will be removed in version {self.higher_version}. message'''
        )







      def       lowerCAmelCase_       (	self  )		->			Any:
        with self.assertWarns(lowerCamelCase  ) as warning:
          deprecate(
              ("""deprecated_arg_1""", self.higher_version, """Hey""")				,    ("""deprecated_arg_2""", self.higher_version, """Hey""")				,    )
        assert (
            str(warning.warnings[0].message  )
            == f'''`deprecated_arg_1` is deprecated and will be removed in version {self.higher_version}. Hey'''
        )
        assert (
            str(warning.warnings[1].message  )
            == f'''`deprecated_arg_2` is deprecated and will be removed in version {self.higher_version}. Hey'''
        )







      def       lowerCAmelCase_       (	self  )		->			Any:







        class 					__lowerCamelCase							:
              lowerCamelCase_      : Dict  			=   5

        with self.assertWarns(lowerCamelCase  ) as warning:
          snake_case_					= deprecate(("""arg""", self.higher_version, """message""")				,    take_from=Args()  )

        assert arg == 5
        assert (
            str(warning.warning  )
            == f'''The `arg` attribute is deprecated and will be removed in version {self.higher_version}. message'''
        )







      def       lowerCAmelCase_       (	self  )		->			Any:







        class 					__lowerCamelCase							:
              lowerCamelCase_      : str  			=   5
              lowerCamelCase_      : List[str]  			=   7

        with self.assertWarns(lowerCamelCase  ) as warning:
          snake_case_		,							snake_case_					= deprecate(
              ("""arg""", self.higher_version, """message""")				,    ("""foo""", self.higher_version, """message""")				,    ("""does not exist""", self.higher_version, """message""")				,    take_from=Args()				,    )

        assert arg_a == 5
        assert arg_a == 7
        assert (
            str(warning.warning  )
            == f'''The `arg` attribute is deprecated and will be removed in version {self.higher_version}. message'''
        )
        assert (
            str(warning.warnings[0].message  )
            == f'''The `arg` attribute is deprecated and will be removed in version {self.higher_version}. message'''
        )
        assert (
            str(warning.warnings[1].message  )
            == f'''The `foo` attribute is deprecated and will be removed in version {self.higher_version}. message'''
        )







      def       lowerCAmelCase_       (	self  )		->			int:
        snake_case_					= {"""deprecated_arg""": 4}

        with self.assertRaises(lowerCamelCase  ) as error:
          deprecate(("""wrong_arg""", self.lower_version, """message""")				,    take_from=lowerCamelCase  )

        assert (
            str(error.exception  )
            == "The deprecation tuple ('wrong_arg', '0.0.1', 'message') should be removed since diffusers' version"
            f''' {__version__} is >= {self.lower_version}'''
        )







      def       lowerCAmelCase_       (	self  )		->			List[Any]:
        with self.assertWarns(lowerCamelCase  ) as warning:
          deprecate(("""deprecated_arg""", self.higher_version, """This message is better!!!""")				,    standard_warn=lowerCamelCase  )

        assert str(warning.warning  ) == "This message is better!!!"







      def       lowerCAmelCase_       (	self  )		->			List[Any]:
        with self.assertWarns(lowerCamelCase  ) as warning:
          deprecate(("""deprecated_arg""", self.higher_version, """This message is better!!!""")				,    standard_warn=lowerCamelCase  )
        assert str(warning.warning  ) == "This message is better!!!"
        assert "diffusers/tests/others/test_utils.py" in warning.filename