




import unittest

from transformers import XLMConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
     import torch

     from transformers import (
         XLMForMultipleChoice,
         XLMForQuestionAnswering,
         XLMForQuestionAnsweringSimple,
         XLMForSequenceClassification,
         XLMForTokenClassification,
         XLMModel,
         XLMWithLMHeadModel,
     )
     from transformers.models.xlm.modeling_xlm import XLM_PRETRAINED_MODEL_ARCHIVE_LIST




class       __lowerCAmelCase				:






       def __init__(      self:    List[str]				,    _lowerCAmelCase:    Dict				,    _lowerCAmelCase:    str=13				,    _lowerCAmelCase:    List[Any]=7				,    _lowerCAmelCase:    Tuple=True				,    _lowerCAmelCase:    Tuple=True				,    _lowerCAmelCase:    Tuple=True				,    _lowerCAmelCase:    Optional[Any]=True				,    _lowerCAmelCase:    Optional[Any]=True				,    _lowerCAmelCase:    Dict=False				,    _lowerCAmelCase:    Union[str, Any]=False				,    _lowerCAmelCase:    List[str]=False				,    _lowerCAmelCase:    Union[str, Any]=2				,    _lowerCAmelCase:    List[str]=99				,    _lowerCAmelCase:    Dict=0				,    _lowerCAmelCase:    int=32				,    _lowerCAmelCase:    Dict=5				,    _lowerCAmelCase:    int=4				,    _lowerCAmelCase:    Optional[Any]=0.1				,    _lowerCAmelCase:    List[str]=0.1				,    _lowerCAmelCase:    Union[str, Any]=5_12				,    _lowerCAmelCase:    List[Any]=2				,    _lowerCAmelCase:    List[str]=0.02				,    _lowerCAmelCase:    List[Any]=2				,    _lowerCAmelCase:    str=4				,    _lowerCAmelCase:    Optional[int]="last"				,    _lowerCAmelCase:    Dict=True				,    _lowerCAmelCase:    List[str]=None				,    _lowerCAmelCase:    List[Any]=0				,    ):
         lowercase			:int							=  parent
         lowercase			:Optional[Any]							=  batch_size
         lowercase			:str							=  seq_length
         lowercase			:str							=  is_training
         lowercase			:Tuple							=  use_input_lengths
         lowercase			:List[Any]							=  use_token_type_ids
         lowercase			:int							=  use_labels
         lowercase			:Union[str, Any]							=  gelu_activation
         lowercase			:str							=  sinusoidal_embeddings
         lowercase			:Tuple							=  causal
         lowercase			:int							=  asm
         lowercase			:Optional[Any]							=  n_langs
         lowercase			:Union[str, Any]							=  vocab_size
         lowercase			:Any							=  n_special
         lowercase			:Any							=  hidden_size
         lowercase			:Dict							=  num_hidden_layers
         lowercase			:Any							=  num_attention_heads
         lowercase			:Union[str, Any]							=  hidden_dropout_prob
         lowercase			:List[str]							=  attention_probs_dropout_prob
         lowercase			:Union[str, Any]							=  max_position_embeddings
         lowercase			:Any							=  type_sequence_label_size
         lowercase			:str							=  initializer_range
         lowercase			:int							=  num_labels
         lowercase			:Optional[int]							=  num_choices
         lowercase			:str							=  summary_type
         lowercase			:List[str]							=  use_proj
         lowercase			:List[str]							=  scope
         lowercase			:Any							=  bos_token_id






       def     SCREAMING_SNAKE_CASE			(      self:    List[str] ):
         lowercase			:List[str]							=  ids_tensor([self.batch_size, self.seq_length]				,    self.vocab_size )
         lowercase			:Union[str, Any]							=  random_attention_mask([self.batch_size, self.seq_length] )

         lowercase			:Union[str, Any]							=  None
         if self.use_input_lengths:
           lowercase			:List[Any]							=  (
               ids_tensor([self.batch_size]				,    vocab_size=2 ) + self.seq_length - 2
           )  # small variation of seq_length

         lowercase			:Optional[Any]							=  None
         if self.use_token_type_ids:
           lowercase			:List[str]							=  ids_tensor([self.batch_size, self.seq_length]				,    self.n_langs )

         lowercase			:Dict							=  None
         lowercase			:Optional[Any]							=  None
         lowercase			:int							=  None
         if self.use_labels:
           lowercase			:str							=  ids_tensor([self.batch_size]				,    self.type_sequence_label_size )
           lowercase			:str							=  ids_tensor([self.batch_size, self.seq_length]				,    self.num_labels )
           lowercase			:Optional[Any]							=  ids_tensor([self.batch_size]				,    2 ).float()
           lowercase			:List[Any]							=  ids_tensor([self.batch_size]				,    self.num_choices )

         lowercase			:Optional[int]							=  self.get_config()

         return (
             config,
             input_ids,
             token_type_ids,
             input_lengths,
             sequence_labels,
             token_labels,
             is_impossible_labels,
             choice_labels,
             input_mask,
         )






       def     SCREAMING_SNAKE_CASE			(      self:    List[str] ):
         return XLMConfig(
             vocab_size=self.vocab_size				,    n_special=self.n_special				,    emb_dim=self.hidden_size				,    n_layers=self.num_hidden_layers				,    n_heads=self.num_attention_heads				,    dropout=self.hidden_dropout_prob				,    attention_dropout=self.attention_probs_dropout_prob				,    gelu_activation=self.gelu_activation				,    sinusoidal_embeddings=self.sinusoidal_embeddings				,    asm=self.asm				,    causal=self.causal				,    n_langs=self.n_langs				,    max_position_embeddings=self.max_position_embeddings				,    initializer_range=self.initializer_range				,    summary_type=self.summary_type				,    use_proj=self.use_proj				,    num_labels=self.num_labels				,    bos_token_id=self.bos_token_id				,    )






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[int]				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Tuple				,    _lowerCAmelCase:    str				,    ):
         lowercase			:Tuple							=  XLMModel(config=_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()
         lowercase			:int							=  model(_lowerCAmelCase				,    lengths=_lowerCAmelCase				,    langs=_lowerCAmelCase )
         lowercase			:int							=  model(_lowerCAmelCase				,    langs=_lowerCAmelCase )
         lowercase			:Optional[Any]							=  model(_lowerCAmelCase )
         self.parent.assertEqual(result.last_hidden_state.shape				,    (self.batch_size, self.seq_length, self.hidden_size) )






       def     SCREAMING_SNAKE_CASE			(      self:    List[Any]				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    List[str]				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    List[str]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    Tuple				,    _lowerCAmelCase:    Tuple				,    _lowerCAmelCase:    Any				,    ):
         lowercase			:Optional[int]							=  XLMWithLMHeadModel(_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()

         lowercase			:Dict							=  model(_lowerCAmelCase				,    token_type_ids=_lowerCAmelCase				,    labels=_lowerCAmelCase )
         self.parent.assertEqual(result.loss.shape				,    () )
         self.parent.assertEqual(result.logits.shape				,    (self.batch_size, self.seq_length, self.vocab_size) )






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    List[str]				,    _lowerCAmelCase:    str				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    Tuple				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    str				,    _lowerCAmelCase:    List[Any]				,    ):
         lowercase			:Optional[int]							=  XLMForQuestionAnsweringSimple(_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()

         lowercase			:Optional[int]							=  model(_lowerCAmelCase )

         lowercase			:Dict							=  model(_lowerCAmelCase				,    start_positions=_lowerCAmelCase				,    end_positions=_lowerCAmelCase )
         lowercase			:Optional[int]							=  outputs
         self.parent.assertEqual(result.start_logits.shape				,    (self.batch_size, self.seq_length) )
         self.parent.assertEqual(result.end_logits.shape				,    (self.batch_size, self.seq_length) )






       def     SCREAMING_SNAKE_CASE			(      self:    Any				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    List[str]				,    _lowerCAmelCase:    Tuple				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    Dict				,    _lowerCAmelCase:    str				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    Any				,    ):
         lowercase			:Any							=  XLMForQuestionAnswering(_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()

         lowercase			:Optional[int]							=  model(_lowerCAmelCase )

         lowercase			:Optional[int]							=  model(
             _lowerCAmelCase				,    start_positions=_lowerCAmelCase				,    end_positions=_lowerCAmelCase				,    cls_index=_lowerCAmelCase				,    is_impossible=_lowerCAmelCase				,    p_mask=_lowerCAmelCase				,    )

         lowercase			:Any							=  model(
             _lowerCAmelCase				,    start_positions=_lowerCAmelCase				,    end_positions=_lowerCAmelCase				,    cls_index=_lowerCAmelCase				,    is_impossible=_lowerCAmelCase				,    )

         ((lowercase)		,			)			:int							=  result_with_labels.to_tuple()

         lowercase			:Union[str, Any]							=  model(_lowerCAmelCase				,    start_positions=_lowerCAmelCase				,    end_positions=_lowerCAmelCase )

         ((lowercase)		,			)			:Optional[Any]							=  result_with_labels.to_tuple()

         self.parent.assertEqual(result_with_labels.loss.shape				,    () )
         self.parent.assertEqual(result.start_top_log_probs.shape				,    (self.batch_size, model.config.start_n_top) )
         self.parent.assertEqual(result.start_top_index.shape				,    (self.batch_size, model.config.start_n_top) )
         self.parent.assertEqual(
             result.end_top_log_probs.shape				,    (self.batch_size, model.config.start_n_top * model.config.end_n_top) )
         self.parent.assertEqual(
             result.end_top_index.shape				,    (self.batch_size, model.config.start_n_top * model.config.end_n_top) )
         self.parent.assertEqual(result.cls_logits.shape				,    (self.batch_size,) )






       def     SCREAMING_SNAKE_CASE			(      self:    Union[str, Any]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    str				,    _lowerCAmelCase:    Dict				,    ):
         lowercase			:Optional[int]							=  XLMForSequenceClassification(_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()

         lowercase			:Dict							=  model(_lowerCAmelCase )
         lowercase			:Optional[int]							=  model(_lowerCAmelCase				,    labels=_lowerCAmelCase )
         self.parent.assertEqual(result.loss.shape				,    () )
         self.parent.assertEqual(result.logits.shape				,    (self.batch_size, self.type_sequence_label_size) )






       def     SCREAMING_SNAKE_CASE			(      self:    str				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Dict				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    Optional[int]				,    ):
         lowercase			:Dict							=  self.num_labels
         lowercase			:Any							=  XLMForTokenClassification(_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()

         lowercase			:List[str]							=  model(_lowerCAmelCase				,    attention_mask=_lowerCAmelCase				,    labels=_lowerCAmelCase )
         self.parent.assertEqual(result.logits.shape				,    (self.batch_size, self.seq_length, self.num_labels) )






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    Dict				,    _lowerCAmelCase:    str				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    Any				,    _lowerCAmelCase:    Tuple				,    ):
         lowercase			:Optional[Any]							=  self.num_choices
         lowercase			:List[str]							=  XLMForMultipleChoice(config=_lowerCAmelCase )
         model.to(_lowerCAmelCase )
         model.eval()
         lowercase			:Tuple							=  input_ids.unsqueeze(1 ).expand(-1				,    self.num_choices				,    -1 ).contiguous()
         lowercase			:List[str]							=  token_type_ids.unsqueeze(1 ).expand(-1				,    self.num_choices				,    -1 ).contiguous()
         lowercase			:int							=  input_mask.unsqueeze(1 ).expand(-1				,    self.num_choices				,    -1 ).contiguous()
         lowercase			:str							=  model(
             _lowerCAmelCase				,    attention_mask=_lowerCAmelCase				,    token_type_ids=_lowerCAmelCase				,    labels=_lowerCAmelCase				,    )
         self.parent.assertEqual(result.logits.shape				,    (self.batch_size, self.num_choices) )






       def     SCREAMING_SNAKE_CASE			(      self:    Union[str, Any] ):
         lowercase			:Tuple							=  self.prepare_config_and_inputs()
         (
             (
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			(
             lowercase
         )		,			
         )			:int							=  config_and_inputs
         lowercase			:List[Any]							=  {"input_ids": input_ids, "token_type_ids": token_type_ids, "lengths": input_lengths}
         return config, inputs_dict







@require_torch
class       __lowerCAmelCase				(							lowerCAmelCase					,       lowerCAmelCase					,       lowerCAmelCase					,       unittest.TestCase):
       _a           =  (
           (
               XLMModel,
               XLMWithLMHeadModel,
               XLMForQuestionAnswering,
               XLMForSequenceClassification,
               XLMForQuestionAnsweringSimple,
               XLMForTokenClassification,
               XLMForMultipleChoice,
           )
           if is_torch_available()
           else ()
       )
       _a           =  (
           (XLMWithLMHeadModel,) if is_torch_available() else ()
       )  # TODO (PVP): Check other models whether language generation is also applicable
       _a           =  (
           {
               '''feature-extraction''': XLMModel,
               '''fill-mask''': XLMWithLMHeadModel,
               '''question-answering''': XLMForQuestionAnsweringSimple,
               '''text-classification''': XLMForSequenceClassification,
               '''text-generation''': XLMWithLMHeadModel,
               '''token-classification''': XLMForTokenClassification,
               '''zero-shot''': XLMForSequenceClassification,
           }
           if is_torch_available()
           else {}
       )






       def     SCREAMING_SNAKE_CASE			(      self:    Any				,    _lowerCAmelCase:    Dict				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    int ):
         if (
             pipeline_test_casse_name == "QAPipelineTests"
             and tokenizer_name is not None
             and not tokenizer_name.endswith("Fast" )
         ):
           # `QAPipelineTests` fails for a few models when the slower tokenizer are used.
           # (The slower tokenizers were never used for pipeline tests before the pipeline testing rework)
           # TODO: check (and possibly fix) the `QAPipelineTests` with slower tokenizer
           return True

         return False






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[int]				,    _lowerCAmelCase:    Union[str, Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    Dict=False ):
         lowercase			:Tuple							=  super()._prepare_for_class(_lowerCAmelCase				,    _lowerCAmelCase				,    return_labels=_lowerCAmelCase )

         if return_labels:
           if model_class.__name__ == "XLMForQuestionAnswering":
             lowercase			:Optional[Any]							=  torch.zeros(
                 self.model_tester.batch_size				,    dtype=torch.long				,    device=_lowerCAmelCase )
             lowercase			:Dict							=  torch.zeros(
                 self.model_tester.batch_size				,    dtype=torch.long				,    device=_lowerCAmelCase )

         return inputs_dict






       def     SCREAMING_SNAKE_CASE			(      self:    int ):
         lowercase			:str							=  XLMModelTester(self )
         lowercase			:Tuple							=  ConfigTester(self				,    config_class=_lowerCAmelCase				,    emb_dim=37 )






       def     SCREAMING_SNAKE_CASE			(      self:    Dict ):
         self.config_tester.run_common_tests()






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[Any] ):
         lowercase			:Any							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_model(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    List[Any] ):
         lowercase			:Any							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_lm_head(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[int] ):
         lowercase			:Union[str, Any]							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_simple_qa(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    Union[str, Any] ):
         lowercase			:Tuple							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_qa(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    Tuple ):
         lowercase			:List[str]							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_sequence_classif(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[Any] ):
         lowercase			:str							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_token_classif(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    int ):
         lowercase			:int							=  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_xlm_for_multiple_choice(*_lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[int]				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    str				,    _lowerCAmelCase:    int				,    _lowerCAmelCase:    List[str]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Any=False				,    _lowerCAmelCase:    Tuple=1 ):
         self.assertIsInstance(_lowerCAmelCase				,    _lowerCAmelCase )
         self.assertListEqual(
             [isinstance(_lowerCAmelCase				,    _lowerCAmelCase ) for iter_attentions in attentions]				,    [True] * len(_lowerCAmelCase ) )
         self.assertEqual(len(_lowerCAmelCase )				,    (max_length - min_length) * num_beam_groups )

         for idx, iter_attentions in enumerate(_lowerCAmelCase ):
           # adds PAD dummy token
           lowercase			:Any							=  min_length + idx + 1
           lowercase			:Tuple							=  min_length + idx + 1

           lowercase			:Union[str, Any]							=  (
               batch_size * num_beam_groups,
               config.num_attention_heads,
               tgt_len,
               src_len,
           )
           # check attn size
           self.assertListEqual(
               [layer_attention.shape for layer_attention in iter_attentions]				,    [expected_shape] * len(_lowerCAmelCase ) )






       def     SCREAMING_SNAKE_CASE			(      self:    List[Any]				,    _lowerCAmelCase:    Optional[int]				,    _lowerCAmelCase:    List[Any]				,    _lowerCAmelCase:    Optional[Any]				,    _lowerCAmelCase:    Tuple				,    _lowerCAmelCase:    Dict				,    _lowerCAmelCase:    Dict=False				,    _lowerCAmelCase:    Dict=1 ):
         self.assertIsInstance(_lowerCAmelCase				,    _lowerCAmelCase )
         self.assertListEqual(
             [isinstance(_lowerCAmelCase				,    _lowerCAmelCase ) for iter_hidden_states in hidden_states]				,    [True] * len(_lowerCAmelCase )				,    )
         self.assertEqual(len(_lowerCAmelCase )				,    (max_length - min_length) * num_beam_groups )

         for idx, iter_hidden_states in enumerate(_lowerCAmelCase ):
           # adds PAD dummy token
           lowercase			:Union[str, Any]							=  min_length + idx + 1
           lowercase			:str							=  (batch_size * num_beam_groups, seq_len, config.hidden_size)
           # check hidden size
           self.assertListEqual(
               [layer_hidden_states.shape for layer_hidden_states in iter_hidden_states]				,    [expected_shape] * len(_lowerCAmelCase )				,    )
         pass






       @slow
       def     SCREAMING_SNAKE_CASE			(      self:    Tuple ):
         for model_name in XLM_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
           lowercase			:Union[str, Any]							=  XLMModel.from_pretrained(_lowerCAmelCase )
           self.assertIsNotNone(_lowerCAmelCase )







@require_torch
class       __lowerCAmelCase				(							unittest.TestCase):






       @slow
       def     SCREAMING_SNAKE_CASE			(      self:    List[str] ):
         lowercase			:Any							=  XLMWithLMHeadModel.from_pretrained("xlm-mlm-en-2048" )
         model.to(_lowerCAmelCase )
         lowercase			:Optional[Any]							=  torch.tensor([[14, 4_47]]				,    dtype=torch.long				,    device=_lowerCAmelCase )  # the president
         lowercase			:List[Any]							=  [
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
             14,
             4_47,
         ]  # the president the president the president the president the president the president the president the president the president the president
         # TODO(PVP): this and other input_ids I tried for generation give pretty bad results. Not sure why. Model might just not be made for auto-regressive inference
         lowercase			:List[Any]							=  model.generate(_lowerCAmelCase				,    do_sample=_lowerCAmelCase )
         self.assertListEqual(output_ids[0].cpu().numpy().tolist()				,    _lowerCAmelCase )









def 					UpperCAmelCase__     (   lowerCamelCase,	lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
  # Return True if there is node that has not iterated.
  lowercase			:Union[str, Any]							=  [False] * len(lowerCamelCase      )
  lowercase			:Union[str, Any]							=  []
  queue.append(lowerCamelCase      )
  lowercase			:Optional[Any]							=  True

  while queue:
    lowercase			:Optional[Any]							=  queue.pop(0      )
    for ind in range(len(graph[u]      )      ):
      if visited[ind] is False and graph[u][ind] > 0:
        queue.append(lowerCamelCase      )
        lowercase			:Dict							=  True
        lowercase			:Dict							=  u

  return visited[t]



def 					UpperCAmelCase__     (   lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
  # This array is filled by BFS and to store path
  lowercase			:Optional[int]							=  [-1] * (len(lowerCamelCase      ))
  lowercase			:int							=  0
  while bfs(lowerCamelCase,	lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
    lowercase			:int							=  float("Inf"      )
    lowercase			:Any							=  sink

    while s != source:
      # Find the minimum value in select path
      lowercase			:Any							=  min(lowerCamelCase,	graph[parent[s]][s]      )
      lowercase			:Dict							=  parent[s]

    max_flow += path_flow
    lowercase			:Union[str, Any]							=  sink

    while v != source:
      lowercase			:List[Any]							=  parent[v]
      graph[u][v] -= path_flow
      graph[v][u] += path_flow
      lowercase			:Any							=  parent[v]
  return max_flow


_UpperCAmelCase		:  Optional[Any]	=   [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0],
]

_UpperCAmelCase	,	_UpperCAmelCase		:  Any	=   0, 5







print(ford_fulkerson(graph, source, sink))



