


snake_case__  				=			float('inf')



class      snake_case__	:
				def __init__(	self  ,   _UpperCAmelCase   ):




										"""simple docstring"""




										__magic_name__					:				Union[str, Any]				=   [0] * n
										__magic_name__					:				Union[str, Any]				=   [0] * n
										__magic_name__					:				Optional[int]				=   [0] * n
										__magic_name__					:				Dict				=   [[] for _ in range(_UpperCAmelCase   )]
				def 			UpperCamelCase_    (	self  ,   _UpperCAmelCase  ,   _UpperCAmelCase  ,   _UpperCAmelCase  ,   _UpperCAmelCase=0   ):




										"""simple docstring"""




										self.adj[a].append([b, len(self.adj[b]   ), c, 0]   )
										self.adj[b].append([a, len(self.adj[a]   ) - 1, rcap, 0]   )
				def 			UpperCamelCase_    (	self  ,   _UpperCAmelCase  ,   _UpperCAmelCase  ,   _UpperCAmelCase   ):




										"""simple docstring"""




										if vertex == sink or not flow:
																return flow

										for i in range(self.ptr[vertex]  ,   len(self.adj[vertex]   )   ):
																__magic_name__					:				Union[str, Any]				=   self.adj[vertex][i]
																if self.lvl[e[0]] == self.lvl[vertex] + 1:
																						__magic_name__					:				Union[str, Any]				=   self.depth_first_search(e[0]  ,   _UpperCAmelCase  ,   min(_UpperCAmelCase  ,   e[2] - e[3]   )   )
																						if p:
																												self.adj[vertex][i][3] += p
																												self.adj[e[0]][e[1]][3] -= p
																												return p
																__magic_name__					:				Dict				=   self.ptr[vertex] + 1
										return 0





				def 			UpperCamelCase_    (	self  ,   _UpperCAmelCase  ,   _UpperCAmelCase   ):




										"""simple docstring"""




										__magic_name__		,			__magic_name__					:				Optional[int]				=   0, source
										for l in range(31   ):  # noqa: E741  l = 30 maybe faster for random data
																while True:
																						__magic_name__		,			__magic_name__					:				List[Any]				=   [0] * len(self.q   ), [0] * len(self.q   )
																						__magic_name__		,			__magic_name__		,			__magic_name__					:				List[str]				=   0, 1, 1
																						while qi < qe and not self.lvl[sink]:
																												__magic_name__					:				Dict				=   self.q[qi]
																												qi += 1
																												for e in self.adj[v]:
																																		if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
																																								__magic_name__					:				Any				=   e[0]
																																								qe += 1
																																								__magic_name__					:				Optional[Any]				=   self.lvl[v] + 1

																						__magic_name__					:				List[Any]				=   self.depth_first_search(_UpperCAmelCase  ,   _UpperCAmelCase  ,   _UpperCAmelCase   )
																						while p:
																												flow += p
																												__magic_name__					:				int				=   self.depth_first_search(_UpperCAmelCase  ,   _UpperCAmelCase  ,   _UpperCAmelCase   )

																						if not self.lvl[sink]:
																												break

										return flow
snake_case__  				=			Dinic(10)
snake_case__  				=			0
snake_case__  				=			9
for vertex in range(1, 5):
			graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
			graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
			graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))






# Copyright 2023 The HuggingFace Team. All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_torch_available,
    is_vision_available,
)


snake_case__  				=			{
    'configuration_tvlt': ['TVLT_PRETRAINED_CONFIG_ARCHIVE_MAP', 'TvltConfig'],
    'feature_extraction_tvlt': ['TvltFeatureExtractor'],
    'processing_tvlt': ['TvltProcessor'],
}

try:
			if not is_torch_available():
						raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
			pass
else:
			snake_case__  				=			[
			    'TVLT_PRETRAINED_MODEL_ARCHIVE_LIST',
			    'TvltModel',
			    'TvltForPreTraining',
			    'TvltForAudioVisualClassification',
			    'TvltPreTrainedModel',
			]

try:
			if not is_vision_available():
						raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
			pass
else:
			snake_case__  				=			['TvltImageProcessor']


if TYPE_CHECKING:
			from .configuration_tvlt import TVLT_PRETRAINED_CONFIG_ARCHIVE_MAP, TvltConfig
			from .processing_tvlt import TvltProcessor
			from .feature_extraction_tvlt import TvltFeatureExtractor

			try:
						if not is_torch_available():
									raise OptionalDependencyNotAvailable()
			except OptionalDependencyNotAvailable:
						pass
			else:
						from .modeling_tvlt import (
						    TVLT_PRETRAINED_MODEL_ARCHIVE_LIST,
						    TvltForAudioVisualClassification,
						    TvltForPreTraining,
						    TvltModel,
						    TvltPreTrainedModel,
						)

			try:
						if not is_vision_available():
									raise OptionalDependencyNotAvailable()
			except OptionalDependencyNotAvailable:
						pass
			else:
						from .image_processing_tvlt import TvltImageProcessor


else:
			import sys

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


