from collections import deque
from math import floor
from random import random
from time import time







class __snake_case				:




   def __init__(    self			:				Dict      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      {}




   def 	__a						(    self			:				Optional[Any]       ,	_lowercase			:				List[str]       ,	_lowercase			:				int       ,	_lowercase			:				Optional[int]=1      ):



     """simple docstring"""






     if self.graph.get(_lowercase      ):
       if self.graph[u].count([w, v]      ) == 0:
         self.graph[u].append([w, v]      )
     else:
       SCREAMING_SNAKE_CASE__										=      [[w, v]]
     if not self.graph.get(_lowercase      ):
       SCREAMING_SNAKE_CASE__										=      []




   def 	__a						(    self			:				Optional[Any]      ):



     """simple docstring"""






     return list(self.graph      )




   def 	__a						(    self			:				int       ,	_lowercase			:				Any       ,	_lowercase			:				Dict      ):



     """simple docstring"""






     if self.graph.get(_lowercase      ):
       for _ in self.graph[u]:
         if _[1] == v:
           self.graph[u].remove(_lowercase      )




   def 	__a						(    self			:				Tuple       ,	_lowercase			:				Any=-2       ,	_lowercase			:				int=-1      ):



     """simple docstring"""






     if s == d:
       return []
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     if s == -2:
       SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      s

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if visited.count(node[1]      ) < 1:
             if node[1] == d:
               visited.append(_lowercase      )
               return visited
             else:
               stack.append(node[1]      )
               visited.append(node[1]      )
               SCREAMING_SNAKE_CASE__										=      node[1]
               break

            # check if all the children are visited
       if s == ss:
         stack.pop()
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return visited




   def 	__a						(    self			:				Any       ,	_lowercase			:				str=-1      ):



     """simple docstring"""






     if c == -1:
       SCREAMING_SNAKE_CASE__										=      floor(random() * 1_00_00      ) + 10
     for i in range(_lowercase      ):
       # every vertex has max 100 edges
       for _ in range(floor(random() * 1_02      ) + 1      ):
         SCREAMING_SNAKE_CASE__										=      floor(random() * c      ) + 1
         if n != i:
           self.add_pair(_lowercase       ,	_lowercase       ,	1      )




   def 	__a						(    self			:				str       ,	_lowercase			:				Dict=-2      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      deque()
     SCREAMING_SNAKE_CASE__										=      []
     if s == -2:
       SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     d.append(_lowercase      )
     visited.append(_lowercase      )
     while d:
       SCREAMING_SNAKE_CASE__										=      d.popleft()
       if len(self.graph[s]      ) != 0:
         for node in self.graph[s]:
           if visited.count(node[1]      ) < 1:
             d.append(node[1]      )
             visited.append(node[1]      )
     return visited




   def 	__a						(    self			:				Optional[Any]       ,	_lowercase			:				Dict      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      0
     for x in self.graph:
       for y in self.graph[x]:
         if y[1] == u:
           count += 1
     return count




   def 	__a						(    self			:				str       ,	_lowercase			:				int      ):



     """simple docstring"""






     return len(self.graph[u]      )




   def 	__a						(    self			:				Tuple       ,	_lowercase			:				List[str]=-2      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     if s == -2:
       SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      s
     SCREAMING_SNAKE_CASE__										=      []

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if visited.count(node[1]      ) < 1:
             stack.append(node[1]      )
             visited.append(node[1]      )
             SCREAMING_SNAKE_CASE__										=      node[1]
             break

            # check if all the children are visited
       if s == ss:
         sorted_nodes.append(stack.pop()      )
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return sorted_nodes




   def 	__a						(    self			:				Tuple      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      -2
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      s
     SCREAMING_SNAKE_CASE__										=      False
     SCREAMING_SNAKE_CASE__										=      set()

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if (
               visited.count(node[1]      ) > 0
               and node[1] != parent
               and indirect_parents.count(node[1]      ) > 0
               and not on_the_way_back
           ):
             SCREAMING_SNAKE_CASE__										=      len(_lowercase      ) - 1
             while len_stack >= 0:
               if stack[len_stack] == node[1]:
                 anticipating_nodes.add(node[1]      )
                 break
               else:
                 anticipating_nodes.add(stack[len_stack]      )
                 len_stack -= 1
           if visited.count(node[1]      ) < 1:
             stack.append(node[1]      )
             visited.append(node[1]      )
             SCREAMING_SNAKE_CASE__										=      node[1]
             break

            # check if all the children are visited
       if s == ss:
         stack.pop()
         SCREAMING_SNAKE_CASE__										=      True
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      False
         indirect_parents.append(_lowercase      )
         SCREAMING_SNAKE_CASE__										=      s
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return list(_lowercase      )




   def 	__a						(    self			:				Optional[int]      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      -2
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      s
     SCREAMING_SNAKE_CASE__										=      False
     SCREAMING_SNAKE_CASE__										=      set()

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if (
               visited.count(node[1]      ) > 0
               and node[1] != parent
               and indirect_parents.count(node[1]      ) > 0
               and not on_the_way_back
           ):
             SCREAMING_SNAKE_CASE__										=      len(_lowercase      ) - 1
             while len_stack_minus_one >= 0:
               if stack[len_stack_minus_one] == node[1]:
                 anticipating_nodes.add(node[1]      )
                 break
               else:
                 return True
           if visited.count(node[1]      ) < 1:
             stack.append(node[1]      )
             visited.append(node[1]      )
             SCREAMING_SNAKE_CASE__										=      node[1]
             break

            # check if all the children are visited
       if s == ss:
         stack.pop()
         SCREAMING_SNAKE_CASE__										=      True
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      False
         indirect_parents.append(_lowercase      )
         SCREAMING_SNAKE_CASE__										=      s
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return False




   def 	__a						(    self			:				Dict       ,	_lowercase			:				Optional[int]=-2       ,	_lowercase			:				Union[str, Any]=-1      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      time()
     self.dfs(_lowercase       ,	_lowercase      )
     SCREAMING_SNAKE_CASE__										=      time()
     return end - begin




   def 	__a						(    self			:				str       ,	_lowercase			:				str=-2      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      time()
     self.bfs(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      time()
     return end - begin







class __snake_case				:




   def __init__(    self			:				Any      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      {}




   def 	__a						(    self			:				List[str]       ,	_lowercase			:				int       ,	_lowercase			:				str       ,	_lowercase			:				Optional[Any]=1      ):



     """simple docstring"""






     if self.graph.get(_lowercase      ):
       # if there already is a edge
       if self.graph[u].count([w, v]      ) == 0:
         self.graph[u].append([w, v]      )
     else:
       # if u does not exist
       SCREAMING_SNAKE_CASE__										=      [[w, v]]
     # add the other way
     if self.graph.get(_lowercase      ):
       # if there already is a edge
       if self.graph[v].count([w, u]      ) == 0:
         self.graph[v].append([w, u]      )
     else:
       # if u does not exist
       SCREAMING_SNAKE_CASE__										=      [[w, u]]




   def 	__a						(    self			:				Optional[Any]       ,	_lowercase			:				Optional[Any]       ,	_lowercase			:				Dict      ):



     """simple docstring"""






     if self.graph.get(_lowercase      ):
       for _ in self.graph[u]:
         if _[1] == v:
           self.graph[u].remove(_lowercase      )
        # the other way round
     if self.graph.get(_lowercase      ):
       for _ in self.graph[v]:
         if _[1] == u:
           self.graph[v].remove(_lowercase      )




   def 	__a						(    self			:				Any       ,	_lowercase			:				List[str]=-2       ,	_lowercase			:				Any=-1      ):



     """simple docstring"""






     if s == d:
       return []
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     if s == -2:
       SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      s

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if visited.count(node[1]      ) < 1:
             if node[1] == d:
               visited.append(_lowercase      )
               return visited
             else:
               stack.append(node[1]      )
               visited.append(node[1]      )
               SCREAMING_SNAKE_CASE__										=      node[1]
               break

            # check if all the children are visited
       if s == ss:
         stack.pop()
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return visited




   def 	__a						(    self			:				str       ,	_lowercase			:				Union[str, Any]=-1      ):



     """simple docstring"""






     if c == -1:
       SCREAMING_SNAKE_CASE__										=      floor(random() * 1_00_00      ) + 10
     for i in range(_lowercase      ):
       # every vertex has max 100 edges
       for _ in range(floor(random() * 1_02      ) + 1      ):
         SCREAMING_SNAKE_CASE__										=      floor(random() * c      ) + 1
         if n != i:
           self.add_pair(_lowercase       ,	_lowercase       ,	1      )




   def 	__a						(    self			:				Optional[Any]       ,	_lowercase			:				Union[str, Any]=-2      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      deque()
     SCREAMING_SNAKE_CASE__										=      []
     if s == -2:
       SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     d.append(_lowercase      )
     visited.append(_lowercase      )
     while d:
       SCREAMING_SNAKE_CASE__										=      d.popleft()
       if len(self.graph[s]      ) != 0:
         for node in self.graph[s]:
           if visited.count(node[1]      ) < 1:
             d.append(node[1]      )
             visited.append(node[1]      )
     return visited




   def 	__a						(    self			:				int       ,	_lowercase			:				List[str]      ):



     """simple docstring"""






     return len(self.graph[u]      )




   def 	__a						(    self			:				int      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      -2
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      s
     SCREAMING_SNAKE_CASE__										=      False
     SCREAMING_SNAKE_CASE__										=      set()

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if (
               visited.count(node[1]      ) > 0
               and node[1] != parent
               and indirect_parents.count(node[1]      ) > 0
               and not on_the_way_back
           ):
             SCREAMING_SNAKE_CASE__										=      len(_lowercase      ) - 1
             while len_stack >= 0:
               if stack[len_stack] == node[1]:
                 anticipating_nodes.add(node[1]      )
                 break
               else:
                 anticipating_nodes.add(stack[len_stack]      )
                 len_stack -= 1
           if visited.count(node[1]      ) < 1:
             stack.append(node[1]      )
             visited.append(node[1]      )
             SCREAMING_SNAKE_CASE__										=      node[1]
             break

            # check if all the children are visited
       if s == ss:
         stack.pop()
         SCREAMING_SNAKE_CASE__										=      True
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      False
         indirect_parents.append(_lowercase      )
         SCREAMING_SNAKE_CASE__										=      s
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return list(_lowercase      )




   def 	__a						(    self			:				Union[str, Any]      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      list(self.graph      )[0]
     stack.append(_lowercase      )
     visited.append(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      -2
     SCREAMING_SNAKE_CASE__										=      []
     SCREAMING_SNAKE_CASE__										=      s
     SCREAMING_SNAKE_CASE__										=      False
     SCREAMING_SNAKE_CASE__										=      set()

     while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]      ) != 0:
         SCREAMING_SNAKE_CASE__										=      s
         for node in self.graph[s]:
           if (
               visited.count(node[1]      ) > 0
               and node[1] != parent
               and indirect_parents.count(node[1]      ) > 0
               and not on_the_way_back
           ):
             SCREAMING_SNAKE_CASE__										=      len(_lowercase      ) - 1
             while len_stack_minus_one >= 0:
               if stack[len_stack_minus_one] == node[1]:
                 anticipating_nodes.add(node[1]      )
                 break
               else:
                 return True
           if visited.count(node[1]      ) < 1:
             stack.append(node[1]      )
             visited.append(node[1]      )
             SCREAMING_SNAKE_CASE__										=      node[1]
             break

            # check if all the children are visited
       if s == ss:
         stack.pop()
         SCREAMING_SNAKE_CASE__										=      True
         if len(_lowercase      ) != 0:
           SCREAMING_SNAKE_CASE__										=      stack[len(_lowercase      ) - 1]
       else:
         SCREAMING_SNAKE_CASE__										=      False
         indirect_parents.append(_lowercase      )
         SCREAMING_SNAKE_CASE__										=      s
         SCREAMING_SNAKE_CASE__										=      ss

       # check if se have reached the starting point
       if len(_lowercase      ) == 0:
         return False




   def 	__a						(    self			:				List[str]      ):



     """simple docstring"""






     return list(self.graph      )




   def 	__a						(    self			:				List[str]       ,	_lowercase			:				Optional[int]=-2       ,	_lowercase			:				int=-1      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      time()
     self.dfs(_lowercase       ,	_lowercase      )
     SCREAMING_SNAKE_CASE__										=      time()
     return end - begin




   def 	__a						(    self			:				Union[str, Any]       ,	_lowercase			:				Any=-2      ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__										=      time()
     self.bfs(_lowercase      )
     SCREAMING_SNAKE_CASE__										=      time()
     return end - begin








import enum
import os
from hashlib import shaaaa
from typing import Optional

from .. import config
from .logging import get_logger


_a      	=  get_logger(__name__)





class __lowerCamelCase (      enum.Enum):





	"""simple docstring"""






	UpperCamelCase__								=      "all_checks"
	UpperCamelCase__								=      "basic_checks"
	UpperCamelCase__								=      "no_checks"





class __lowerCamelCase (      snake_case__):





	"""simple docstring"""











class __lowerCamelCase (      snake_case__):





	"""simple docstring"""











class __lowerCamelCase (      snake_case__):





	"""simple docstring"""











class __lowerCamelCase (      snake_case__):





	"""simple docstring"""









def __A    (      __lowerCAmelCase ,		__lowerCAmelCase ,		__lowerCAmelCase=None	)->  str:





						"""simple docstring"""



						if expected_checksums is None:
												logger.info('Unable to verify checksums.'	)
												return
						if len(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	) > 0:
												raise ExpectedMoreDownloadedFiles(str(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	)	)
						if len(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	) > 0:
												raise UnexpectedDownloadedFile(str(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	)	)
						_UpperCAmelCase									=			[url for url in expected_checksums if expected_checksums[url] != recorded_checksums[url]]
						_UpperCAmelCase									=			' for ' + verification_name if verification_name is not None else ''
						if len(__lowerCAmelCase	) > 0:
												raise NonMatchingChecksumError(
												    F"""Checksums didn't match{for_verification_name}:\n"""
												    F"""{bad_urls}\n"""
												    'Set `verification_mode=\'no_checks\'` to skip checksums verification and ignore this error'	)
						logger.info('All the checksums matched successfully' + for_verification_name	)





class __lowerCamelCase (      snake_case__):





	"""simple docstring"""











class __lowerCamelCase (      snake_case__):





	"""simple docstring"""











class __lowerCamelCase (      snake_case__):





	"""simple docstring"""











class __lowerCamelCase (      snake_case__):





	"""simple docstring"""









def __A    (      __lowerCAmelCase ,		__lowerCAmelCase	)->  int:





						"""simple docstring"""



						if expected_splits is None:
												logger.info('Unable to verify splits sizes.'	)
												return
						if len(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	) > 0:
												raise ExpectedMoreSplits(str(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	)	)
						if len(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	) > 0:
												raise UnexpectedSplits(str(set(__lowerCAmelCase	) - set(__lowerCAmelCase	)	)	)
						_UpperCAmelCase									=			[
						    {'expected': expected_splits[name], 'recorded': recorded_splits[name]}
						    for name in expected_splits
						    if expected_splits[name].num_examples != recorded_splits[name].num_examples
						]
						if len(__lowerCAmelCase	) > 0:
												raise NonMatchingSplitsSizesError(str(__lowerCAmelCase	)	)
						logger.info('All the splits matched successfully.'	)


def __A    (      __lowerCAmelCase ,		__lowerCAmelCase = True	)->  dict:





						"""simple docstring"""



						if record_checksum:
												_UpperCAmelCase									=			shaaaa()
												with open(__lowerCAmelCase ,		'rb'	) as f:
																		for chunk in iter(lambda: f.read(1 << 20	) ,		b''	):
																								m.update(__lowerCAmelCase	)
																		_UpperCAmelCase									=			m.hexdigest()
						else:
												_UpperCAmelCase									=			None
						return {"num_bytes": os.path.getsize(__lowerCAmelCase	), "checksum": checksum}


def __A    (      __lowerCAmelCase	)->  List[str]:





						"""simple docstring"""



						if dataset_size and config.IN_MEMORY_MAX_SIZE:
												return dataset_size < config.IN_MEMORY_MAX_SIZE
						else:
												return False
