




import os
import sys
import unittest


_UpperCAmelCase		:  List[str]	=   os.path.abspath(os.path.dirname(os.path.dirname(os.path.dirname(__file__))))
sys.path.append(os.path.join(git_repo_path, "utils"))

import check_dummies  # noqa: E402
from check_dummies import create_dummy_files, create_dummy_object, find_backend, read_init  # noqa: E402


# Align TRANSFORMERS_PATH in check_dummies with the current path
_UpperCAmelCase		:  int	=   os.path.join(git_repo_path, "src", "transformers")

_UpperCAmelCase		:  Dict	=   "\n{0} = None\n"

_UpperCAmelCase		:  Optional[Any]	=   "\nclass {0}(metaclass=DummyObject):\n    _backends = {1}\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, {1})\n"


_UpperCAmelCase		:  List[str]	=   "\ndef {0}(*args, **kwargs):\n    requires_backends({0}, {1})\n"




class       __lowerCAmelCase				(							unittest.TestCase):






       def     SCREAMING_SNAKE_CASE			(      self:    Union[str, Any] ):
         lowercase			:Tuple							=  find_backend("    _import_structure[\"models.albert\"].append(\"AlbertTokenizerFast\")" )
         self.assertIsNone(_lowerCAmelCase )

         lowercase			:str							=  find_backend("    if not is_tokenizers_available():" )
         self.assertEqual(_lowerCAmelCase				,    "tokenizers" )

         lowercase			:int							=  find_backend("    if not is_tensorflow_text_available():" )
         self.assertEqual(_lowerCAmelCase				,    "tensorflow_text" )

         lowercase			:Any							=  find_backend("    if not (is_sentencepiece_available() and is_tokenizers_available()):" )
         self.assertEqual(_lowerCAmelCase				,    "sentencepiece_and_tokenizers" )

         lowercase			:Tuple							=  find_backend(
             "    if not (is_sentencepiece_available() and is_tensorflow_text_available()):" )
         self.assertEqual(_lowerCAmelCase				,    "sentencepiece_and_tensorflow_text" )

         lowercase			:Optional[int]							=  find_backend(
             "    if not (is_sentencepiece_available() and is_tokenizers_available() and is_vision_available()):" )
         self.assertEqual(_lowerCAmelCase				,    "sentencepiece_and_tokenizers_and_vision" )






       def     SCREAMING_SNAKE_CASE			(      self:    int ):
         lowercase			:List[str]							=  read_init()
         # We don't assert on the exact list of keys to allow for smooth grow of backend-specific objects
         self.assertIn("torch"				,    _lowerCAmelCase )
         self.assertIn("tensorflow_text"				,    _lowerCAmelCase )
         self.assertIn("sentencepiece_and_tokenizers"				,    _lowerCAmelCase )

         # Likewise, we can't assert on the exact content of a key
         self.assertIn("BertModel"				,    objects["torch"] )
         self.assertIn("TFBertModel"				,    objects["tf"] )
         self.assertIn("FlaxBertModel"				,    objects["flax"] )
         self.assertIn("BertModel"				,    objects["torch"] )
         self.assertIn("TFBertTokenizer"				,    objects["tensorflow_text"] )
         self.assertIn("convert_slow_tokenizer"				,    objects["sentencepiece_and_tokenizers"] )






       def     SCREAMING_SNAKE_CASE			(      self:    List[Any] ):
         lowercase			:str							=  create_dummy_object("CONSTANT"				,    "'torch'" )
         self.assertEqual(_lowerCAmelCase				,    "\nCONSTANT = None\n" )

         lowercase			:Tuple							=  create_dummy_object("function"				,    "'torch'" )
         self.assertEqual(
             _lowerCAmelCase				,    "\ndef function(*args, **kwargs):\n    requires_backends(function, 'torch')\n" )

         lowercase			:List[Any]							=  "\nclass FakeClass(metaclass=DummyObject):\n    _backends = 'torch'\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, 'torch')\n"
         lowercase			:Tuple							=  create_dummy_object("FakeClass"				,    "'torch'" )
         self.assertEqual(_lowerCAmelCase				,    _lowerCAmelCase )






       def     SCREAMING_SNAKE_CASE			(      self:    str ):
         lowercase			:int							=  "# This file is autogenerated by the command `make fix-copies`, do not edit.\nfrom ..utils import DummyObject, requires_backends\n\n\nCONSTANT = None\n\n\ndef function(*args, **kwargs):\n    requires_backends(function, [\"torch\"])\n\n\nclass FakeClass(metaclass=DummyObject):\n    _backends = [\"torch\"]\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, [\"torch\"])\n"
         lowercase			:List[str]							=  create_dummy_files({"torch": ["CONSTANT", "function", "FakeClass"]} )
         self.assertEqual(dummy_files["torch"]				,    _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))



