



from collections import deque





def 						a__     (						_UpperCamelCase     :	List[str]							):
   return input(_UpperCamelCase							).strip().split(''' '''							)





def 						a__     (						_UpperCamelCase     :	int	,_UpperCamelCase     :	int							):
   __lowerCamelCase  							=      {}
   for i in range(_UpperCamelCase							):
      __lowerCamelCase  							=      []

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





def 						a__     (						_UpperCamelCase     :	int	,_UpperCamelCase     :	int							):
   __lowerCamelCase  							=      {}
   for i in range(_UpperCamelCase							):
      __lowerCamelCase  							=      []

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





def 						a__     (						_UpperCamelCase     :	int	,_UpperCamelCase     :	int							):
   __lowerCamelCase  							=      {}
   for i in range(_UpperCamelCase							):
      __lowerCamelCase  							=      []

   for e in range(_UpperCamelCase							):
      __lowerCamelCase							,__lowerCamelCase							,__lowerCamelCase  							=      (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__":
  a_						,  a_								=   (int(i) for i in _input("""Number of nodes and edges: """))

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

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





def 						a__     (						_UpperCamelCase     :	Optional[int]	,_UpperCamelCase     :	List[str]							):
   __lowerCamelCase							,__lowerCamelCase  							=      {s}, [s]
   print(_UpperCamelCase							)
   while _s:
      __lowerCamelCase  							=      0
      for i in g[_s[-1]]:
         if i not in vis:
            _s.append(_UpperCamelCase							)
            vis.add(_UpperCamelCase							)
            __lowerCamelCase  							=      1
            print(_UpperCamelCase							)
            break
      if not flag:
         _s.pop()





def 						a__     (						_UpperCamelCase     :	List[Any]	,_UpperCamelCase     :	List[Any]							):
   __lowerCamelCase							,__lowerCamelCase  							=      {s}, deque([s]							)
   print(_UpperCamelCase							)
   while q:
      __lowerCamelCase  							=      q.popleft()
      for v in g[u]:
         if v not in vis:
            vis.add(_UpperCamelCase							)
            q.append(_UpperCamelCase							)
            print(_UpperCamelCase							)





def 						a__     (						_UpperCamelCase     :	Optional[int]	,_UpperCamelCase     :	List[Any]							):
   __lowerCamelCase							,__lowerCamelCase							,__lowerCamelCase  							=      {s: 0}, set(), {s: 0}
   while True:
      if len(_UpperCamelCase							) == len(_UpperCamelCase							) - 1:
         break
      __lowerCamelCase  							=      10_00_00
      for i in dist:
         if i not in known and dist[i] < mini:
            __lowerCamelCase  							=      dist[i]
            __lowerCamelCase  							=      i
      known.add(_UpperCamelCase							)
      for v in g[u]:
         if v[0] not in known and dist[u] + v[1] < dist.get(v[0]	,10_00_00							):
            __lowerCamelCase  							=      dist[u] + v[1]
            __lowerCamelCase  							=      u
   for i in dist:
      if i != s:
         print(dist[i]							)





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





def 						a__     (						):
   __lowerCamelCase  							=      input().strip()
   __lowerCamelCase  							=      []
   for _ in range(_UpperCamelCase							):
      a.append(map(_UpperCamelCase	,input().strip().split()							)							)
   return a, n





def 						a__     (						_UpperCamelCase     :	int							):
   ((__lowerCamelCase)							,(__lowerCamelCase))  							=      a_and_n
   __lowerCamelCase  							=      list(_UpperCamelCase							)
   __lowerCamelCase  							=      [[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]:
               __lowerCamelCase  							=      dist[i][k] + dist[k][j]
               __lowerCamelCase  							=      k
   print(_UpperCamelCase							)





def 						a__     (						_UpperCamelCase     :	Tuple	,_UpperCamelCase     :	Union[str, Any]							):
   __lowerCamelCase							,__lowerCamelCase							,__lowerCamelCase  							=      {s: 0}, set(), {s: 0}
   while True:
      if len(_UpperCamelCase							) == len(_UpperCamelCase							) - 1:
         break
      __lowerCamelCase  							=      10_00_00
      for i in dist:
         if i not in known and dist[i] < mini:
            __lowerCamelCase  							=      dist[i]
            __lowerCamelCase  							=      i
      known.add(_UpperCamelCase							)
      for v in g[u]:
         if v[0] not in known and v[1] < dist.get(v[0]	,10_00_00							):
            __lowerCamelCase  							=      v[1]
            __lowerCamelCase  							=      u
   return dist





def 						a__     (						):
   __lowerCamelCase							,__lowerCamelCase  							=      map(_UpperCamelCase	,input().split(''' '''							)							)
   __lowerCamelCase  							=      []
   for _ in range(_UpperCamelCase							):
      edges.append(map(_UpperCamelCase	,input().split(''' '''							)							)							)
   return edges, n





def 						a__     (						_UpperCamelCase     :	str							):
   # Sort edges on the basis of distance
   ((__lowerCamelCase)							,(__lowerCamelCase))  							=      e_and_n
   e.sort(reverse=_UpperCamelCase	,key=lambda _UpperCamelCase							: x[2]							)
   __lowerCamelCase  							=      [{i} for i in range(1	,n + 1							)]
   while True:
      if len(_UpperCamelCase							) == 1:
         break
      print(_UpperCamelCase							)
      __lowerCamelCase  							=      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 						a__     (						_UpperCamelCase     :	Optional[Any]							):
   __lowerCamelCase  							=      []
   for node in graph:
      if not graph[node]:
         isolated.append(_UpperCamelCase							)
   return isolated











import json
from typing import List, Optional, Tuple

from tokenizers import pre_tokenizers, processors

from ...tokenization_utils_base import AddedToken, BatchEncoding
from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import logging
from .tokenization_longformer import LongformerTokenizer


a_								=   logging.get_logger(__name__)

a_								=   {"""vocab_file""": """vocab.json""", """merges_file""": """merges.txt""", """tokenizer_file""": """tokenizer.json"""}

a_								=   {
    """vocab_file""": {
        """allenai/longformer-base-4096""": """https://huggingface.co/allenai/longformer-base-4096/resolve/main/vocab.json""",
        """allenai/longformer-large-4096""": (
            """https://huggingface.co/allenai/longformer-large-4096/resolve/main/vocab.json"""
        ),
        """allenai/longformer-large-4096-finetuned-triviaqa""": (
            """https://huggingface.co/allenai/longformer-large-4096-finetuned-triviaqa/resolve/main/vocab.json"""
        ),
        """allenai/longformer-base-4096-extra.pos.embd.only""": (
            """https://huggingface.co/allenai/longformer-base-4096-extra.pos.embd.only/resolve/main/vocab.json"""
        ),
        """allenai/longformer-large-4096-extra.pos.embd.only""": (
            """https://huggingface.co/allenai/longformer-large-4096-extra.pos.embd.only/resolve/main/vocab.json"""
        ),
    },
    """merges_file""": {
        """allenai/longformer-base-4096""": """https://huggingface.co/allenai/longformer-base-4096/resolve/main/merges.txt""",
        """allenai/longformer-large-4096""": (
            """https://huggingface.co/allenai/longformer-large-4096/resolve/main/merges.txt"""
        ),
        """allenai/longformer-large-4096-finetuned-triviaqa""": (
            """https://huggingface.co/allenai/longformer-large-4096-finetuned-triviaqa/resolve/main/merges.txt"""
        ),
        """allenai/longformer-base-4096-extra.pos.embd.only""": (
            """https://huggingface.co/allenai/longformer-base-4096-extra.pos.embd.only/resolve/main/merges.txt"""
        ),
        """allenai/longformer-large-4096-extra.pos.embd.only""": (
            """https://huggingface.co/allenai/longformer-large-4096-extra.pos.embd.only/resolve/main/merges.txt"""
        ),
    },
    """tokenizer_file""": {
        """allenai/longformer-base-4096""": (
            """https://huggingface.co/allenai/longformer-base-4096/resolve/main/tokenizer.json"""
        ),
        """allenai/longformer-large-4096""": (
            """https://huggingface.co/allenai/longformer-large-4096/resolve/main/tokenizer.json"""
        ),
        """allenai/longformer-large-4096-finetuned-triviaqa""": (
            """https://huggingface.co/allenai/longformer-large-4096-finetuned-triviaqa/resolve/main/tokenizer.json"""
        ),
        """allenai/longformer-base-4096-extra.pos.embd.only""": (
            """https://huggingface.co/allenai/longformer-base-4096-extra.pos.embd.only/resolve/main/tokenizer.json"""
        ),
        """allenai/longformer-large-4096-extra.pos.embd.only""": (
            """https://huggingface.co/allenai/longformer-large-4096-extra.pos.embd.only/resolve/main/tokenizer.json"""
        ),
    },
}

a_								=   {
    """allenai/longformer-base-4096""": 4_096,
    """allenai/longformer-large-4096""": 4_096,
    """allenai/longformer-large-4096-finetuned-triviaqa""": 4_096,
    """allenai/longformer-base-4096-extra.pos.embd.only""": 4_096,
    """allenai/longformer-large-4096-extra.pos.embd.only""": 4_096,
}



class 	__lowerCAmelCase       (		lowerCAmelCase__				):
 lowerCAmelCase__       =					VOCAB_FILES_NAMES
 lowerCAmelCase__       =					PRETRAINED_VOCAB_FILES_MAP
 lowerCAmelCase__       =					PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
 lowerCAmelCase__       =					["""input_ids""", """attention_mask"""]
 lowerCAmelCase__       =					LongformerTokenizer




 def __init__(  self		,			__UpperCAmelCase=None		,			__UpperCAmelCase=None		,			__UpperCAmelCase=None		,			__UpperCAmelCase="replace"		,			__UpperCAmelCase="<s>"		,			__UpperCAmelCase="</s>"		,			__UpperCAmelCase="</s>"		,			__UpperCAmelCase="<s>"		,			__UpperCAmelCase="<unk>"		,			__UpperCAmelCase="<pad>"		,			__UpperCAmelCase="<mask>"		,			__UpperCAmelCase=False		,			__UpperCAmelCase=True		,			**__UpperCAmelCase		,			):



    '''simple docstring'''
    super().__init__(
        __UpperCAmelCase		,			__UpperCAmelCase		,			tokenizer_file=__UpperCAmelCase		,			errors=__UpperCAmelCase		,			bos_token=__UpperCAmelCase		,			eos_token=__UpperCAmelCase		,			sep_token=__UpperCAmelCase		,			cls_token=__UpperCAmelCase		,			unk_token=__UpperCAmelCase		,			pad_token=__UpperCAmelCase		,			mask_token=__UpperCAmelCase		,			add_prefix_space=__UpperCAmelCase		,			trim_offsets=__UpperCAmelCase		,			**__UpperCAmelCase		,			)

    __lowerCamelCase  							=      json.loads(self.backend_tokenizer.pre_tokenizer.__getstate__()			)
    if pre_tok_state.get('''add_prefix_space'''		,			__UpperCAmelCase			) != add_prefix_space:
       __lowerCamelCase  							=      getattr(__UpperCAmelCase		,			pre_tok_state.pop('''type'''			)			)
       __lowerCamelCase  							=      add_prefix_space
       __lowerCamelCase  							=      pre_tok_class(**__UpperCAmelCase			)

    __lowerCamelCase  							=      add_prefix_space

    __lowerCamelCase  							=      '''post_processor'''
    __lowerCamelCase  							=      getattr(self.backend_tokenizer		,			__UpperCAmelCase		,			__UpperCAmelCase			)
    if tokenizer_component_instance:
       __lowerCamelCase  							=      json.loads(tokenizer_component_instance.__getstate__()			)

       # The lists 'sep' and 'cls' must be cased in tuples for the object `post_processor_class`
       if "sep" in state:
          __lowerCamelCase  							=      tuple(state['''sep''']			)
       if "cls" in state:
          __lowerCamelCase  							=      tuple(state['''cls''']			)

       __lowerCamelCase  							=      False

       if state.get('''add_prefix_space'''		,			__UpperCAmelCase			) != add_prefix_space:
          __lowerCamelCase  							=      add_prefix_space
          __lowerCamelCase  							=      True

       if state.get('''trim_offsets'''		,			__UpperCAmelCase			) != trim_offsets:
          __lowerCamelCase  							=      trim_offsets
          __lowerCamelCase  							=      True

       if changes_to_apply:
          __lowerCamelCase  							=      getattr(__UpperCAmelCase		,			state.pop('''type'''			)			)
          __lowerCamelCase  							=      component_class(**__UpperCAmelCase			)
          setattr(self.backend_tokenizer		,			__UpperCAmelCase		,			__UpperCAmelCase			)




 @property
 def     lowerCamelCase (  self			):



    '''simple docstring'''
    if self._mask_token is None:
       if self.verbose:
          logger.error('''Using mask_token, but it is not set yet.'''			)
       return None
    return str(self._mask_token			)




 @mask_token.setter
 def     lowerCamelCase (  self		,			__UpperCAmelCase			):



    '''simple docstring'''
    __lowerCamelCase  							=      AddedToken(__UpperCAmelCase		,			lstrip=__UpperCAmelCase		,			rstrip=__UpperCAmelCase			) if isinstance(__UpperCAmelCase		,			__UpperCAmelCase			) else value
    __lowerCamelCase  							=      value




 def     lowerCamelCase (  self		,			*__UpperCAmelCase		,			**__UpperCAmelCase			):



    '''simple docstring'''
    __lowerCamelCase  							=      kwargs.get('''is_split_into_words'''		,			__UpperCAmelCase			)
    assert self.add_prefix_space or not is_split_into_words, (
        F"""You need to instantiate {self.__class__.__name__} with add_prefix_space=True """
        "to use it with pretokenized inputs."
    )

    return super()._batch_encode_plus(*__UpperCAmelCase		,			**__UpperCAmelCase			)




 def     lowerCamelCase (  self		,			*__UpperCAmelCase		,			**__UpperCAmelCase			):



    '''simple docstring'''
    __lowerCamelCase  							=      kwargs.get('''is_split_into_words'''		,			__UpperCAmelCase			)

    assert self.add_prefix_space or not is_split_into_words, (
        F"""You need to instantiate {self.__class__.__name__} with add_prefix_space=True """
        "to use it with pretokenized inputs."
    )

    return super()._encode_plus(*__UpperCAmelCase		,			**__UpperCAmelCase			)




 def     lowerCamelCase (  self		,			__UpperCAmelCase		,			__UpperCAmelCase = None			):



    '''simple docstring'''
    __lowerCamelCase  							=      self._tokenizer.model.save(__UpperCAmelCase		,			name=__UpperCAmelCase			)
    return tuple(__UpperCAmelCase			)




 def     lowerCamelCase (  self		,			__UpperCAmelCase		,			__UpperCAmelCase=None			):



    '''simple docstring'''
    __lowerCamelCase  							=      [self.bos_token_id] + token_ids_a + [self.eos_token_id]
    if token_ids_a is None:
       return output

    return output + [self.eos_token_id] + token_ids_a + [self.eos_token_id]




 def     lowerCamelCase (  self		,			__UpperCAmelCase		,			__UpperCAmelCase = None			):



    '''simple docstring'''
    __lowerCamelCase  							=      [self.sep_token_id]
    __lowerCamelCase  							=      [self.cls_token_id]

    if token_ids_a is None:
       return len(cls + token_ids_a + sep			) * [0]
    return len(cls + token_ids_a + sep + sep + token_ids_a + sep			) * [0]






