






from collections import deque





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

     '''simple docstring'''
     return input(__lowerCamelCase					).strip().split(""" """					)





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

     '''simple docstring'''
     UpperCAmelCase__			:     dict[int, list[int]]										= {}
     for i in range(__lowerCamelCase					):
          UpperCAmelCase__			:     Union[str, Any]										= []

     for e in range(__lowerCamelCase					):
          UpperCAmelCase__			,		UpperCAmelCase__			:     List[str]										= (int(__lowerCamelCase					) for i in _input(F"Edge {e + 1}: <node1> <node2> "					))
          graph[x].append(__lowerCamelCase					)
     return graph





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

     '''simple docstring'''
     UpperCAmelCase__			:     dict[int, list[int]]										= {}
     for i in range(__lowerCamelCase					):
          UpperCAmelCase__			:     Union[str, Any]										= []

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





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

     '''simple docstring'''
     UpperCAmelCase__			:     dict[int, list[tuple[int, int]]]										= {}
     for i in range(__lowerCamelCase					):
          UpperCAmelCase__			:     str										= []

     for e in range(__lowerCamelCase					):
          UpperCAmelCase__			,		UpperCAmelCase__			,		UpperCAmelCase__			:     Dict										= (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__":
      SCREAMING_SNAKE_CASE__							, SCREAMING_SNAKE_CASE__		:       Optional[int]   							=							(int(i) for i in _input("""Number of nodes and edges: """))

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

      SCREAMING_SNAKE_CASE__		:       int   							=							{
          1: initialize_unweighted_directed_graph,
          2: initialize_unweighted_undirected_graph,
          3: initialize_weighted_undirected_graph,
      }[graph_choice](n, m)





def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase					)   -> Any:

     '''simple docstring'''
     UpperCAmelCase__			,		UpperCAmelCase__			:     List[Any]										= {s}, [s]
     print(__lowerCamelCase					)
     while _s:
          UpperCAmelCase__			:     int										= 0
          for i in g[_s[-1]]:
               if i not in vis:
                    _s.append(__lowerCamelCase					)
                    vis.add(__lowerCamelCase					)
                    UpperCAmelCase__			:     Dict										= 1
                    print(__lowerCamelCase					)
                    break
          if not flag:
               _s.pop()





def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase					)   -> int:

     '''simple docstring'''
     UpperCAmelCase__			,		UpperCAmelCase__			:     Any										= {s}, deque([s]					)
     print(__lowerCamelCase					)
     while q:
          UpperCAmelCase__			:     Optional[Any]										= q.popleft()
          for v in g[u]:
               if v not in vis:
                    vis.add(__lowerCamelCase					)
                    q.append(__lowerCamelCase					)
                    print(__lowerCamelCase					)





def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase					)   -> Tuple:

     '''simple docstring'''
     UpperCAmelCase__			,		UpperCAmelCase__			,		UpperCAmelCase__			:     int										= {s: 0}, set(), {s: 0}
     while True:
          if len(__lowerCamelCase					) == len(__lowerCamelCase					) - 1:
               break
          UpperCAmelCase__			:     Any										= 10_0000
          for i in dist:
               if i not in known and dist[i] < mini:
                    UpperCAmelCase__			:     List[str]										= dist[i]
                    UpperCAmelCase__			:     Dict										= 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_0000					):
                    UpperCAmelCase__			:     int										= dist[u] + v[1]
                    UpperCAmelCase__			:     Tuple										= u
     for i in dist:
          if i != s:
               print(dist[i]					)





def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase=None   ,       __lowerCamelCase=None					)   -> Union[str, Any]:

     '''simple docstring'''
     if q is None:
          UpperCAmelCase__			:     List[Any]										= [1]
     if ind is None:
          UpperCAmelCase__			:     Dict										= [0] * (len(__lowerCamelCase					) + 1)  # SInce oth Index is ignored
          for u in g:
               for v in g[u]:
                    ind[v] += 1
          UpperCAmelCase__			:     Union[str, Any]										= deque()
          for i in g:
               if ind[i] == 0:
                    q.append(__lowerCamelCase					)
     if len(__lowerCamelCase					) == 0:
          return
     UpperCAmelCase__			:     List[str]										= q.popleft()
     print(__lowerCamelCase					)
     for w in g[v]:
          ind[w] -= 1
          if ind[w] == 0:
               q.append(__lowerCamelCase					)
     topo(__lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase					)





def    _lowerCamelCase	(	)   -> str:

     '''simple docstring'''
     UpperCAmelCase__			:     List[Any]										= input().strip()
     UpperCAmelCase__			:     Tuple										= []
     for _ in range(__lowerCamelCase					):
          a.append(map(__lowerCamelCase   ,       input().strip().split()					)					)
     return a, n





def    _lowerCamelCase	(	__lowerCamelCase					)   -> Tuple:

     '''simple docstring'''
     ((UpperCAmelCase__)			,		(UpperCAmelCase__))			:     Optional[Any]										= a_and_n
     UpperCAmelCase__			:     Any										= list(__lowerCamelCase					)
     UpperCAmelCase__			:     Any										= [[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]:
                         UpperCAmelCase__			:     List[str]										= dist[i][k] + dist[k][j]
                         UpperCAmelCase__			:     Optional[Any]										= k
     print(__lowerCamelCase					)





def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase					)   -> Optional[int]:

     '''simple docstring'''
     UpperCAmelCase__			,		UpperCAmelCase__			,		UpperCAmelCase__			:     Any										= {s: 0}, set(), {s: 0}
     while True:
          if len(__lowerCamelCase					) == len(__lowerCamelCase					) - 1:
               break
          UpperCAmelCase__			:     List[str]										= 10_0000
          for i in dist:
               if i not in known and dist[i] < mini:
                    UpperCAmelCase__			:     str										= dist[i]
                    UpperCAmelCase__			:     Union[str, Any]										= i
          known.add(__lowerCamelCase					)
          for v in g[u]:
               if v[0] not in known and v[1] < dist.get(v[0]   ,       10_0000					):
                    UpperCAmelCase__			:     List[str]										= v[1]
                    UpperCAmelCase__			:     Any										= u
     return dist





def    _lowerCamelCase	(	)   -> List[str]:

     '''simple docstring'''
     UpperCAmelCase__			,		UpperCAmelCase__			:     Union[str, Any]										= map(__lowerCamelCase   ,       input().split(""" """					)					)
     UpperCAmelCase__			:     List[str]										= []
     for _ in range(__lowerCamelCase					):
          edges.append(map(__lowerCamelCase   ,       input().split(""" """					)					)					)
     return edges, n





def    _lowerCamelCase	(	__lowerCamelCase					)   -> Optional[int]:

     '''simple docstring'''
     # Sort edges on the basis of distance
     ((UpperCAmelCase__)			,		(UpperCAmelCase__))			:     int										= e_and_n
     e.sort(reverse=__lowerCamelCase   ,       key=lambda __lowerCamelCase					: x[2]					)
     UpperCAmelCase__			:     str										= [{i} for i in range(1   ,       n + 1					)]
     while True:
          if len(__lowerCamelCase					) == 1:
               break
          print(__lowerCamelCase					)
          UpperCAmelCase__			:     Tuple										= 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    _lowerCamelCase	(	__lowerCamelCase					)   -> Union[str, Any]:

     '''simple docstring'''
     UpperCAmelCase__			:     Optional[Any]										= []
     for node in graph:
          if not graph[node]:
               isolated.append(__lowerCamelCase					)
     return isolated














import warnings

from ...utils import logging
from .image_processing_vilt import ViltImageProcessor


SCREAMING_SNAKE_CASE__		:       Optional[int]   							=							logging.get_logger(__name__)







class 							UpperCAmelCase_     (		__lowerCamelCase		):




     def __init__(							self  ,	*_lowerCAmelCase  ,	**_lowerCAmelCase		):
          warnings.warn(
              """The class ViltFeatureExtractor is deprecated and will be removed in version 5 of Transformers. Please"""
              """ use ViltImageProcessor instead."""  ,	_lowerCAmelCase  ,	)
          super().__init__(*_lowerCAmelCase  ,	**_lowerCAmelCase		)






