'''simple docstring'''





import json
import multiprocessing
import os
import re
from collections import defaultdict

import torch
from accelerate import Accelerator
from accelerate.utils import set_seed
from arguments import HumanEvalArguments
from datasets import load_dataset, load_metric
from torch.utils.data import IterableDataset
from torch.utils.data.dataloader import DataLoader
from tqdm import tqdm

import transformers
from transformers import AutoModelForCausalLM, AutoTokenizer, HfArgumentParser, StoppingCriteria, StoppingCriteriaList


SCREAMING_SNAKE_CASE_:	Union[str, Any]    =['\nclass', '\ndef', '\n#', '\n@', '\nprint', '\nif']




class 			__A (					UpperCamelCase__      ):



    def __init__(self       :       Optional[Any]  ,     __a       :       str  ,     __a       :       Optional[Any]  ,     __a       :       int=None  ,     __a       :       str=1					):
         UpperCAmelCase_			       =  tokenizer
         UpperCAmelCase_			       =  dataset
         UpperCAmelCase_			       =  len(__a					) if n_tasks is None else n_tasks
         UpperCAmelCase_			       =  n_copies






    def __iter__(self       :       List[Any]					):
         UpperCAmelCase_			       =  []
         for task in range(self.n_tasks					):
              # without strip, the model generate commented codes ...
              prompts.append(self.tokenizer.eos_token + self.dataset[task]["prompt"].strip()					)
         UpperCAmelCase_			       =  self.tokenizer(__a  ,     padding=__a  ,     return_tensors="pt"					)
         for task in range(self.n_tasks					):
              for _ in range(self.n_copies					):
                   yield {
                       "ids": outputs.input_ids[task],
                       "task_id": task,
                       "input_len": outputs.attention_mask[task].sum(),
                   }




class 			__A (					UpperCamelCase__      ):



    def __init__(self       :       List[Any]  ,     __a       :       Any  ,     __a       :       Any  ,     __a       :       Dict					):
         UpperCAmelCase_			       =  start_length
         UpperCAmelCase_			       =  eof_strings
         UpperCAmelCase_			       =  tokenizer






    def __call__(self       :       Dict  ,     __a       :       List[Any]  ,     __a       :       int  ,     **__a       :       Dict					):
         UpperCAmelCase_			       =  self.tokenizer.batch_decode(input_ids[:, self.start_length :]					)
         UpperCAmelCase_			       =  []
         for decoded_generation in decoded_generations:
              done.append(any(stop_string in decoded_generation for stop_string in self.eof_strings					)					)
         return all(__a					)





def       lowerCAmelCase_							(   snake_case_			:					Union[str, Any]     )       -> Optional[Any]:


     '''simple docstring'''




     UpperCAmelCase_			       =  re.split("(%s)" % "|".join(snake_case_     )   ,       snake_case_     )
     # last string should be ""
     return "".join(string_list[:-2]     )





def       lowerCAmelCase_							(   snake_case_			:					Optional[int]   ,       snake_case_			:					List[Any]   ,       snake_case_			:					List[str]   ,       snake_case_			:					Tuple   ,       snake_case_			:					Optional[Any]   ,       snake_case_			:					Tuple=20   ,       **snake_case_			:					Any     )       -> Tuple:


     '''simple docstring'''




     UpperCAmelCase_			       =  defaultdict(snake_case_     )  # dict of list of generated tokens
     for step, batch in tqdm(enumerate(snake_case_     )     ):
          with torch.no_grad():
               UpperCAmelCase_			       =  batch["ids"].shape[-1]
               UpperCAmelCase_			       =  accelerator.unwrap_model(snake_case_     ).generate(
                   input_ids=batch["ids"][:, : batch["input_len"]]   ,       num_return_sequences=snake_case_   ,       **snake_case_     )
               # each task is generated batch_size times
               UpperCAmelCase_			       =  batch["task_id"].repeat(snake_case_     )
               UpperCAmelCase_			       =  accelerator.pad_across_processes(
                   snake_case_   ,       dim=1   ,       pad_index=tokenizer.pad_token_id     )

               UpperCAmelCase_       ,					UpperCAmelCase_			       =  accelerator.gather((generated_tokens, generated_tasks)     )
               UpperCAmelCase_			       =  generated_tokens.cpu().numpy()
               UpperCAmelCase_			       =  generated_tasks.cpu().numpy()

               for task, generated_tokens in zip(snake_case_   ,       snake_case_     ):
                    gen_token_dict[task].append(snake_case_     )

     UpperCAmelCase_			       =  [[] for _ in range(snake_case_     )]
     for task, generated_tokens in gen_token_dict.items():
          for s in generated_tokens:
               UpperCAmelCase_			       =  tokenizer.decode(snake_case_   ,       skip_special_tokens=snake_case_   ,       clean_up_tokenization_spaces=snake_case_     )
               code_gens[task].append(remove_last_block(snake_case_     )     )
     return code_gens





def       lowerCAmelCase_							(   )       -> Optional[Any]:


     '''simple docstring'''




     UpperCAmelCase_			       =  HfArgumentParser(snake_case_     )
     UpperCAmelCase_			       =  parser.parse_args()

     transformers.logging.set_verbosity_error()
     # enables code execution in code_eval metric
     UpperCAmelCase_			       =  args.HF_ALLOW_CODE_EVAL
     # make sure tokenizer plays nice with multiprocessing
     UpperCAmelCase_			       =  "false"

     if args.num_workers is None:
          UpperCAmelCase_			       =  multiprocessing.cpu_count()

     # Use dataset load to feed to accelerate
     UpperCAmelCase_			       =  Accelerator()
     set_seed(args.seed   ,       device_specific=snake_case_     )

     # Load model and tokenizer
     UpperCAmelCase_			       =  AutoTokenizer.from_pretrained(args.model_ckpt     )
     UpperCAmelCase_			       =  tokenizer.eos_token
     UpperCAmelCase_			       =  AutoModelForCausalLM.from_pretrained(args.model_ckpt     )

     # Generation settings
     UpperCAmelCase_			       =  {
         "do_sample": args.do_sample,
         "temperature": args.temperature,
         "max_new_tokens": args.max_new_tokens,
         "top_p": args.top_p,
         "top_k": args.top_k,
         "stopping_criteria": StoppingCriteriaList([EndOfFunctionCriteria(0   ,       snake_case_   ,       snake_case_     )]     ),
     }

     # Load evaluation dataset and metric
     UpperCAmelCase_			       =  load_dataset("openai_humaneval"     )
     UpperCAmelCase_			       =  load_metric("code_eval"     )

     UpperCAmelCase_			       =  args.num_tasks if args.num_tasks is not None else len(human_eval["test"]     )
     UpperCAmelCase_			       =  args.n_samples // args.batch_size

     UpperCAmelCase_			       =  TokenizedDataset(snake_case_   ,       human_eval["test"]   ,       n_copies=snake_case_   ,       n_tasks=snake_case_     )
     # do not confuse args.batch_size, which is actually the num_return_sequences
     UpperCAmelCase_			       =  DataLoader(snake_case_   ,       batch_size=1     )

     # Run a quick test to see if code evaluation is enabled
     try:
          UpperCAmelCase_			       =  code_eval_metric.compute(references=[""]   ,       predictions=[[""]]     )
     except ValueError as exception:
          print(
              "Code evaluation not enabled. Read the warning below carefully and then use `--HF_ALLOW_CODE_EVAL=\"1\"`"
              " flag to enable code evaluation."     )
          raise exception

     UpperCAmelCase_       ,					UpperCAmelCase_			       =  accelerator.prepare(snake_case_   ,       snake_case_     )

     UpperCAmelCase_			       =  complete_code(
         snake_case_   ,       snake_case_   ,       snake_case_   ,       snake_case_   ,       n_tasks=snake_case_   ,       batch_size=args.batch_size   ,       **snake_case_   ,       )

     if accelerator.is_main_process:
          UpperCAmelCase_			       =  []

          for task in tqdm(range(snake_case_     )     ):
               UpperCAmelCase_			       =  human_eval["test"][task]["test"]
               UpperCAmelCase_			       =  f"""check({human_eval["test"][task]["entry_point"]})"""
               references.append("\n" + test_func + "\n" + entry_point     )

          # Evaluate completions with "code_eval" metric
          UpperCAmelCase_       ,					UpperCAmelCase_			       =  code_eval_metric.compute(
              references=snake_case_   ,       predictions=snake_case_   ,       num_workers=args.num_workers     )
          print(f"""Results: {pass_at_k}"""     )

          # Save results to json file
          with open(args.output_file   ,       "w"     ) as fp:
               json.dump(snake_case_   ,       snake_case_     )


# For some reason the folliwng seems to be necessary sometimes for code_eval to work nice with multiprocessing
# https://stackoverflow.com/questions/60804599/python-multiprocessing-keeps-spawning-the-whole-script
if __name__ == "__main__":
    main()





'''simple docstring'''

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


class     __UpperCAmelCase       :





  def __init__(	self ):
     lowerCAmelCase_			=      {}





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=1 ):
     if self.graph.get(_lowerCamelCase ):
        if self.graph[u].count([w, v] ) == 0:
           self.graph[u].append([w, v] )
     else:
        lowerCAmelCase_			=      [[w, v]]
     if not self.graph.get(_lowerCamelCase ):
        lowerCAmelCase_			=      []





  def 						UpperCAmelCase_	(	self ):
     return list(self.graph )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     if self.graph.get(_lowerCamelCase ):
        for _ in self.graph[u]:
           if _[1] == v:
              self.graph[u].remove(_lowerCamelCase )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     if s == d:
        return []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s

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

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-1 ):
     if c == -1:
        lowerCAmelCase_			=      floor(random() * 1_0000 ) + 10
     for i in range(_lowerCamelCase ):
        # every vertex has max 100 edges
        for _ in range(floor(random() * 102 ) + 1 ):
           lowerCAmelCase_			=      floor(random() * c ) + 1
           if n != i:
              self.add_pair(_lowerCamelCase    ,     _lowerCamelCase    ,     1 )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      deque()
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     d.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     while d:
        lowerCAmelCase_			=      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 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      0
     for x in self.graph:
        for y in self.graph[x]:
           if y[1] == u:
              count += 1
     return count





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     return len(self.graph[u] )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      []

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

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      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
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 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] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      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
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 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] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     lowerCAmelCase_			=      time()
     self.dfs(_lowerCamelCase    ,     _lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      time()
     self.bfs(_lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin






class     __UpperCAmelCase       :





  def __init__(	self ):
     lowerCAmelCase_			=      {}





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=1 ):
     # check if the u exists
     if self.graph.get(_lowerCamelCase ):
        # 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
        lowerCAmelCase_			=      [[w, v]]
     # add the other way
     if self.graph.get(_lowerCamelCase ):
        # 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
        lowerCAmelCase_			=      [[w, u]]





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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     if s == d:
        return []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s

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

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-1 ):
     if c == -1:
        lowerCAmelCase_			=      floor(random() * 1_0000 ) + 10
     for i in range(_lowerCamelCase ):
        # every vertex has max 100 edges
        for _ in range(floor(random() * 102 ) + 1 ):
           lowerCAmelCase_			=      floor(random() * c ) + 1
           if n != i:
              self.add_pair(_lowerCamelCase    ,     _lowerCamelCase    ,     1 )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      deque()
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     d.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     while d:
        lowerCAmelCase_			=      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 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     return len(self.graph[u] )





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      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
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 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] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      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
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 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] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self ):
     return list(self.graph )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     lowerCAmelCase_			=      time()
     self.dfs(_lowerCamelCase    ,     _lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      time()
     self.bfs(_lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin





