




from collections import deque







def 			_UpperCamelCase (_lowerCamelCase							:     List[Any]	)->   Any:




     '''simple docstring'''





     return input(_lowerCamelCase	).strip().split(''' '''	)







def 			_UpperCamelCase (_lowerCamelCase							:     int   ,	_lowerCamelCase							:     int	)->   dict[int, list[int]]:




     '''simple docstring'''





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

     for e in range(_lowerCamelCase	):
          __snake_case					,    __snake_case    					=  (int(_lowerCamelCase	) for i in _input(f'''Edge {e + 1}: <node1> <node2> '''	))
          graph[x].append(_lowerCamelCase	)
     return graph







def 			_UpperCamelCase (_lowerCamelCase							:     int   ,	_lowerCamelCase							:     int	)->   dict[int, list[int]]:




     '''simple docstring'''





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

     for e in range(_lowerCamelCase	):
          __snake_case					,    __snake_case    					=  (int(_lowerCamelCase	) for i in _input(f'''Edge {e + 1}: <node1> <node2> '''	))
          graph[x].append(_lowerCamelCase	)
          graph[y].append(_lowerCamelCase	)
     return graph







def 			_UpperCamelCase (_lowerCamelCase							:     int   ,	_lowerCamelCase							:     int	)->   dict[int, list[tuple[int, int]]]:




     '''simple docstring'''





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

     for e in range(_lowerCamelCase	):
          __snake_case					,    __snake_case					,    __snake_case    					=  (int(_lowerCamelCase	) 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_       :  Optional[Any]      =		(int(i) for i in _input('''Number of nodes and edges: '''))

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

     UpperCAmelCase_       :  Optional[Any]      =		{
         1: initialize_unweighted_directed_graph,
         2: initialize_unweighted_undirected_graph,
         3: initialize_weighted_undirected_graph,
     }[graph_choice](n, m)







def 			_UpperCamelCase (_lowerCamelCase							:     str   ,	_lowerCamelCase							:     int	)->   str:




     '''simple docstring'''





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







def 			_UpperCamelCase (_lowerCamelCase							:     Union[str, Any]   ,	_lowerCamelCase							:     List[str]	)->   int:




     '''simple docstring'''





     __snake_case					,    __snake_case    					=  {s}, deque([s]	)
     print(_lowerCamelCase	)
     while q:
          __snake_case    					=  q.popleft()
          for v in g[u]:
               if v not in vis:
                    vis.add(_lowerCamelCase	)
                    q.append(_lowerCamelCase	)
                    print(_lowerCamelCase	)







def 			_UpperCamelCase (_lowerCamelCase							:     Optional[int]   ,	_lowerCamelCase							:     Any	)->   Dict:




     '''simple docstring'''





     __snake_case					,    __snake_case					,    __snake_case    					=  {s: 0}, set(), {s: 0}
     while True:
          if len(_lowerCamelCase	) == len(_lowerCamelCase	) - 1:
               break
          __snake_case    					=  10_00_00
          for i in dist:
               if i not in known and dist[i] < mini:
                    __snake_case    					=  dist[i]
                    __snake_case    					=  i
          known.add(_lowerCamelCase	)
          for v in g[u]:
               if v[0] not in known and dist[u] + v[1] < dist.get(v[0]   ,	10_00_00	):
                    __snake_case    					=  dist[u] + v[1]
                    __snake_case    					=  u
     for i in dist:
          if i != s:
               print(dist[i]	)







def 			_UpperCamelCase (_lowerCamelCase							:     Dict   ,	_lowerCamelCase							:     Union[str, Any]=None   ,	_lowerCamelCase							:     str=None	)->   List[str]:




     '''simple docstring'''





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







def 			_UpperCamelCase ()->   Optional[Any]:




     '''simple docstring'''





     __snake_case    					=  input().strip()
     __snake_case    					=  []
     for _ in range(_lowerCamelCase	):
          a.append(map(_lowerCamelCase   ,	input().strip().split()	)	)
     return a, n







def 			_UpperCamelCase (_lowerCamelCase							:     Dict	)->   Union[str, Any]:




     '''simple docstring'''





     ((__snake_case)					,    (__snake_case))    					=  a_and_n
     __snake_case    					=  list(_lowerCamelCase	)
     __snake_case    					=  [[0] * n for i in range(_lowerCamelCase	)]
     for k in range(_lowerCamelCase	):
          for i in range(_lowerCamelCase	):
               for j in range(_lowerCamelCase	):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                         __snake_case    					=  dist[i][k] + dist[k][j]
                         __snake_case    					=  k
     print(_lowerCamelCase	)







def 			_UpperCamelCase (_lowerCamelCase							:     List[str]   ,	_lowerCamelCase							:     Any	)->   str:




     '''simple docstring'''





     __snake_case					,    __snake_case					,    __snake_case    					=  {s: 0}, set(), {s: 0}
     while True:
          if len(_lowerCamelCase	) == len(_lowerCamelCase	) - 1:
               break
          __snake_case    					=  10_00_00
          for i in dist:
               if i not in known and dist[i] < mini:
                    __snake_case    					=  dist[i]
                    __snake_case    					=  i
          known.add(_lowerCamelCase	)
          for v in g[u]:
               if v[0] not in known and v[1] < dist.get(v[0]   ,	10_00_00	):
                    __snake_case    					=  v[1]
                    __snake_case    					=  u
     return dist







def 			_UpperCamelCase ()->   Dict:




     '''simple docstring'''





     __snake_case					,    __snake_case    					=  map(_lowerCamelCase   ,	input().split(''' '''	)	)
     __snake_case    					=  []
     for _ in range(_lowerCamelCase	):
          edges.append(map(_lowerCamelCase   ,	input().split(''' '''	)	)	)
     return edges, n







def 			_UpperCamelCase (_lowerCamelCase							:     str	)->   Tuple:




     '''simple docstring'''





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







def 			_UpperCamelCase (_lowerCamelCase							:     List[str]	)->   Optional[Any]:




     '''simple docstring'''





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












'''simple docstring'''



from transformers import ProcessorMixin





class     lowerCAmelCase   ( __lowerCAmelCase):
       __lowercase  :      Union[str, Any]        =			'''AutoFeatureExtractor'''
       __lowercase  :      List[Any]        =			'''AutoTokenizer'''






