






"""simple docstring"""


from collections import deque



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

  for e in range(__UpperCamelCase					):
    __A     ,       __A     ,       __A		     =					(int(__UpperCamelCase					) 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__":
       lowercase_	,						lowercase_								=	(int(i) for i in _input('Number of nodes and edges: '))

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

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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase=None						,			__UpperCamelCase=None					):




  """simple docstring"""







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



def    lowerCAmelCase							(       ):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       ):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







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





def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







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











from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_sentencepiece_available,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


snake_case__   :				Any						=	{
    'configuration_camembert': ['CAMEMBERT_PRETRAINED_CONFIG_ARCHIVE_MAP', 'CamembertConfig', 'CamembertOnnxConfig'],
}

try:
       if not is_sentencepiece_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       snake_case__   :				List[Any]						=	['CamembertTokenizer']

try:
       if not is_tokenizers_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       snake_case__   :				Dict						=	['CamembertTokenizerFast']

try:
       if not is_torch_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       snake_case__   :				Any						=	[
           'CAMEMBERT_PRETRAINED_MODEL_ARCHIVE_LIST',
           'CamembertForCausalLM',
           'CamembertForMaskedLM',
           'CamembertForMultipleChoice',
           'CamembertForQuestionAnswering',
           'CamembertForSequenceClassification',
           'CamembertForTokenClassification',
           'CamembertModel',
           'CamembertPreTrainedModel',
       ]

try:
       if not is_tf_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       snake_case__   :				Any						=	[
           'TF_CAMEMBERT_PRETRAINED_MODEL_ARCHIVE_LIST',
           'TFCamembertForCausalLM',
           'TFCamembertForMaskedLM',
           'TFCamembertForMultipleChoice',
           'TFCamembertForQuestionAnswering',
           'TFCamembertForSequenceClassification',
           'TFCamembertForTokenClassification',
           'TFCamembertModel',
           'TFCamembertPreTrainedModel',
       ]


if TYPE_CHECKING:
       from .configuration_camembert import CAMEMBERT_PRETRAINED_CONFIG_ARCHIVE_MAP, CamembertConfig, CamembertOnnxConfig

       try:
              if not is_sentencepiece_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .tokenization_camembert import CamembertTokenizer

       try:
              if not is_tokenizers_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .tokenization_camembert_fast import CamembertTokenizerFast

       try:
              if not is_torch_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_camembert import (
                  CAMEMBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
                  CamembertForCausalLM,
                  CamembertForMaskedLM,
                  CamembertForMultipleChoice,
                  CamembertForQuestionAnswering,
                  CamembertForSequenceClassification,
                  CamembertForTokenClassification,
                  CamembertModel,
                  CamembertPreTrainedModel,
              )

       try:
              if not is_tf_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_tf_camembert import (
                  TF_CAMEMBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
                  TFCamembertForCausalLM,
                  TFCamembertForMaskedLM,
                  TFCamembertForMultipleChoice,
                  TFCamembertForQuestionAnswering,
                  TFCamembertForSequenceClassification,
                  TFCamembertForTokenClassification,
                  TFCamembertModel,
                  TFCamembertPreTrainedModel,
              )

else:
       import sys

       snake_case__   :				Any						=	_LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)





