


class    lowerCamelCase__     :





     def __init__(self	,  UpperCAmelCase )  ->     Dict:
      _lowercase							   =data
      _lowercase							   =None
      _lowercase							   =None





     def __str__(self )  ->     Dict:
      return f"{self.data}"







class    lowerCamelCase__     :





     def __init__(self )  ->     str:
      _lowercase							   =None
      _lowercase							   =None





     def __iter__(self )  ->     int:
      _lowercase							   =self.head
      while node:
       yield node.data
       _lowercase							   =node.next





     def __str__(self )  ->     Optional[int]:
      return "->".join([str(UpperCAmelCase ) for item in self] )





     def __len__(self )  ->     Any:
      return sum(1 for _ in self )





     def   __A      (self	,  UpperCAmelCase )  ->     List[Any]:
      self.insert_at_nth(0	,  UpperCAmelCase )





     def   __A      (self	,  UpperCAmelCase )  ->     List[Any]:
      self.insert_at_nth(len(self )	,  UpperCAmelCase )





     def   __A      (self	,  UpperCAmelCase	,  UpperCAmelCase )  ->     Union[str, Any]:
      _lowercase							   =len(self )

      if not 0 <= index <= length:
       raise IndexError('''list index out of range''' )
      _lowercase							   =Node(UpperCAmelCase )
      if self.head is None:
       _lowercase							   =_lowercase							   =new_node
      elif index == 0:
       _lowercase							   =new_node
       _lowercase							   =self.head
       _lowercase							   =new_node
      elif index == length:
       _lowercase							   =new_node
       _lowercase							   =self.tail
       _lowercase							   =new_node
      else:
       _lowercase							   =self.head
       for _ in range(0	,  UpperCAmelCase ):
        _lowercase							   =temp.next
       _lowercase							   =new_node
       _lowercase							   =temp.previous
       _lowercase							   =temp
       _lowercase							   =new_node





     def   __A      (self )  ->     int:
      return self.delete_at_nth(0 )





     def   __A      (self )  ->     str:
      return self.delete_at_nth(len(self ) - 1 )





     def   __A      (self	,  UpperCAmelCase )  ->     Optional[int]:
      _lowercase							   =len(self )

      if not 0 <= index <= length - 1:
       raise IndexError('''list index out of range''' )
      _lowercase							   =self.head  # default first node
      if length == 1:
       _lowercase							   =_lowercase							   =None
      elif index == 0:
       _lowercase							   =self.head.next
       _lowercase							   =None
      elif index == length - 1:
       _lowercase							   =self.tail
       _lowercase							   =self.tail.previous
       _lowercase							   =None
      else:
       _lowercase							   =self.head
       for _ in range(0	,  UpperCAmelCase ):
        _lowercase							   =temp.next
       _lowercase							   =temp
       _lowercase							   =temp.previous
       _lowercase							   =temp.next
      return delete_node.data





     def   __A      (self	,  UpperCAmelCase )  ->     str:
      _lowercase							   =self.head

      while current.data != data:  # Find the position to delete
       if current.next:
        _lowercase							   =current.next
       else:  # We have reached the end an no value matches
        raise ValueError('''No data matching given value''' )

      if current == self.head:
       self.delete_head()

      elif current == self.tail:
       self.delete_tail()

      else:  # Before: 1 <--> 2(current) <--> 3
       _lowercase							   =current.next  # 1 --> 3
       _lowercase							   =current.previous  # 1 <--> 3
      return data





     def   __A      (self )  ->     Optional[Any]:
      return len(self ) == 0



def        UpperCAmelCase_      (							)  ->    None:







 """simple docstring"""


 _lowercase							   =DoublyLinkedList()
 assert linked_list.is_empty() is True
 assert str(__snake_case		) == ""

 try:
  linked_list.delete_head()
  raise AssertionError  # This should not happen.
 except IndexError:
  assert True  # This should happen.

 try:
  linked_list.delete_tail()
  raise AssertionError  # This should not happen.
 except IndexError:
  assert True  # This should happen.

 for i in range(10		):
  assert len(__snake_case		) == i
  linked_list.insert_at_nth(__snake_case  ,		i + 1		)
 assert str(__snake_case		) == "->".join(str(__snake_case		) for i in range(1  ,		11		)		)

 linked_list.insert_at_head(0		)
 linked_list.insert_at_tail(11		)
 assert str(__snake_case		) == "->".join(str(__snake_case		) for i in range(0  ,		12		)		)

 assert linked_list.delete_head() == 0
 assert linked_list.delete_at_nth(9		) == 10
 assert linked_list.delete_tail() == 11
 assert len(__snake_case		) == 9
 assert str(__snake_case		) == "->".join(str(__snake_case		) for i in range(1  ,		10		)		)


if __name__ == "__main__":
  from doctest import testmod

  testmod()





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







 """simple docstring"""


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







 """simple docstring"""


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

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







 """simple docstring"""


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

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







 """simple docstring"""


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

 for e in range(__snake_case		):
  _lowercase   ,					_lowercase   ,					_lowercase							   =(int(__snake_case		) 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		)  ->    Tuple:







 """simple docstring"""


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







 """simple docstring"""


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







 """simple docstring"""


 _lowercase   ,					_lowercase   ,					_lowercase							   ={s: 0}, set(), {s: 0}
 while True:
  if len(__snake_case		) == len(__snake_case		) - 1:
   break
  _lowercase							   =100000
  for i in dist:
   if i not in known and dist[i] < mini:
    _lowercase							   =dist[i]
    _lowercase							   =i
  known.add(__snake_case		)
  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(__snake_case		) + 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(__snake_case		)
 if len(__snake_case		) == 0:
  return
 _lowercase							   =q.popleft()
 print(__snake_case		)
 for w in g[v]:
  ind[w] -= 1
  if ind[w] == 0:
   q.append(__snake_case		)
 topo(__snake_case  ,		__snake_case  ,		__snake_case		)
def        UpperCAmelCase_      (							)  ->    Tuple:







 """simple docstring"""


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







 """simple docstring"""


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







 """simple docstring"""


 _lowercase   ,					_lowercase   ,					_lowercase							   ={s: 0}, set(), {s: 0}
 while True:
  if len(__snake_case		) == len(__snake_case		) - 1:
   break
  _lowercase							   =100000
  for i in dist:
   if i not in known and dist[i] < mini:
    _lowercase							   =dist[i]
    _lowercase							   =i
  known.add(__snake_case		)
  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(__snake_case  ,		input().split(''' '''		)		)
 _lowercase							   =[]
 for _ in range(__snake_case		):
  edges.append(map(__snake_case  ,		input().split(''' '''		)		)		)
 return edges, n
def        UpperCAmelCase_      (							__snake_case		)  ->    str:







 """simple docstring"""


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



def        UpperCAmelCase_      (							__snake_case		)  ->    Tuple:







 """simple docstring"""


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

