





"""simple docstring"""






import unittest

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

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 (
        MPNetForMaskedLM,
        MPNetForMultipleChoice,
        MPNetForQuestionAnswering,
        MPNetForSequenceClassification,
        MPNetForTokenClassification,
        MPNetModel,
    )



class 	snake_case					:






       def __init__(   self    ,  a__    ,  a__=13    ,  a__=7    ,  a__=True    ,  a__=True    ,  a__=False    ,  a__=True    ,  a__=99    ,  a__=64    ,  a__=5    ,  a__=4    ,  a__=64    ,  a__="gelu"    ,  a__=0.1    ,  a__=0.1    ,  a__=5_12    ,  a__=16    ,  a__=2    ,  a__=0.02    ,  a__=3    ,  a__=4    ,  a__=None    ,  ):
              _UpperCAmelCase     =     parent
              _UpperCAmelCase     =     batch_size
              _UpperCAmelCase     =     seq_length
              _UpperCAmelCase     =     is_training
              _UpperCAmelCase     =     use_input_mask
              _UpperCAmelCase     =     use_token_type_ids
              _UpperCAmelCase     =     use_labels
              _UpperCAmelCase     =     vocab_size
              _UpperCAmelCase     =     hidden_size
              _UpperCAmelCase     =     num_hidden_layers
              _UpperCAmelCase     =     num_attention_heads
              _UpperCAmelCase     =     intermediate_size
              _UpperCAmelCase     =     hidden_act
              _UpperCAmelCase     =     hidden_dropout_prob
              _UpperCAmelCase     =     attention_probs_dropout_prob
              _UpperCAmelCase     =     max_position_embeddings
              _UpperCAmelCase     =     type_vocab_size
              _UpperCAmelCase     =     type_sequence_label_size
              _UpperCAmelCase     =     initializer_range
              _UpperCAmelCase     =     num_labels
              _UpperCAmelCase     =     num_choices
              _UpperCAmelCase     =     scope






       def 							__A (   self     ):
              return MPNetConfig.from_pretrained('microsoft/mpnet-base'     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     ids_tensor([self.batch_size, self.seq_length]    ,  self.vocab_size     )

              _UpperCAmelCase     =     None
              if self.use_input_mask:
                     _UpperCAmelCase     =     random_attention_mask([self.batch_size, self.seq_length]     )

              _UpperCAmelCase     =     None
              _UpperCAmelCase     =     None
              _UpperCAmelCase     =     None
              if self.use_labels:
                     _UpperCAmelCase     =     ids_tensor([self.batch_size]    ,  self.type_sequence_label_size     )
                     _UpperCAmelCase     =     ids_tensor([self.batch_size, self.seq_length]    ,  self.num_labels     )
                     _UpperCAmelCase     =     ids_tensor([self.batch_size]    ,  self.num_choices     )

              _UpperCAmelCase     =     self.get_config()
              return config, input_ids, input_mask, sequence_labels, token_labels, choice_labels






       def 							__A (   self     ):
              return MPNetConfig(
                  vocab_size=self.vocab_size    ,  hidden_size=self.hidden_size    ,  num_hidden_layers=self.num_hidden_layers    ,  num_attention_heads=self.num_attention_heads    ,  intermediate_size=self.intermediate_size    ,  hidden_act=self.hidden_act    ,  hidden_dropout_prob=self.hidden_dropout_prob    ,  attention_probs_dropout_prob=self.attention_probs_dropout_prob    ,  max_position_embeddings=self.max_position_embeddings    ,  initializer_range=self.initializer_range    ,  )






       def 							__A (   self    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__     ):
              _UpperCAmelCase     =     MPNetModel(config=a__     )
              model.to(a__     )
              model.eval()
              _UpperCAmelCase     =     model(a__    ,  a__     )
              _UpperCAmelCase     =     model(a__     )
              self.parent.assertEqual(result.last_hidden_state.shape    ,  (self.batch_size, self.seq_length, self.hidden_size)     )
              self.parent.assertEqual(result.pooler_output.shape    ,  (self.batch_size, self.hidden_size)     )






       def 							__A (   self    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__     ):
              _UpperCAmelCase     =     MPNetForQuestionAnswering(config=a__     )
              model.to(a__     )
              model.eval()
              _UpperCAmelCase     =     model(
                  a__    ,  attention_mask=a__    ,  start_positions=a__    ,  end_positions=a__    ,  )
              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 							__A (   self    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__     ):
              _UpperCAmelCase     =     self.num_labels
              _UpperCAmelCase     =     MPNetForSequenceClassification(a__     )
              model.to(a__     )
              model.eval()
              _UpperCAmelCase     =     model(a__    ,  attention_mask=a__    ,  labels=a__     )
              self.parent.assertEqual(result.logits.shape    ,  (self.batch_size, self.num_labels)     )






       def 							__A (   self    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__     ):
              _UpperCAmelCase     =     self.num_choices
              _UpperCAmelCase     =     MPNetForMultipleChoice(config=a__     )
              model.to(a__     )
              model.eval()
              _UpperCAmelCase     =     input_ids.unsqueeze(1     ).expand(-1    ,  self.num_choices    ,  -1     ).contiguous()
              _UpperCAmelCase     =     input_mask.unsqueeze(1     ).expand(-1    ,  self.num_choices    ,  -1     ).contiguous()
              _UpperCAmelCase     =     model(
                  a__    ,  attention_mask=a__    ,  labels=a__    ,  )
              self.parent.assertEqual(result.logits.shape    ,  (self.batch_size, self.num_choices)     )






       def 							__A (   self    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__     ):
              _UpperCAmelCase     =     self.num_labels
              _UpperCAmelCase     =     MPNetForTokenClassification(config=a__     )
              model.to(a__     )
              model.eval()
              _UpperCAmelCase     =     model(a__    ,  attention_mask=a__    ,  labels=a__     )
              self.parent.assertEqual(result.logits.shape    ,  (self.batch_size, self.seq_length, self.num_labels)     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     self.prepare_config_and_inputs()
              ((_UpperCAmelCase)    ,							(_UpperCAmelCase)    ,							(_UpperCAmelCase)    ,							(_UpperCAmelCase)    ,							(_UpperCAmelCase)    ,							(_UpperCAmelCase))     =     config_and_inputs
              _UpperCAmelCase     =     {'input_ids': input_ids, 'attention_mask': input_mask}
              return config, inputs_dict



@require_torch
class 	snake_case					(      snake_case			,	snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  (
           (
               MPNetForMaskedLM,
               MPNetForMultipleChoice,
               MPNetForQuestionAnswering,
               MPNetForSequenceClassification,
               MPNetForTokenClassification,
               MPNetModel,
           )
           if is_torch_available()
           else ()
       )
       lowerCAmelCase__						 =  (
           {
               """feature-extraction""": MPNetModel,
               """fill-mask""": MPNetForMaskedLM,
               """question-answering""": MPNetForQuestionAnswering,
               """text-classification""": MPNetForSequenceClassification,
               """token-classification""": MPNetForTokenClassification,
               """zero-shot""": MPNetForSequenceClassification,
           }
           if is_torch_available()
           else {}
       )
       lowerCAmelCase__						 =  False
       lowerCAmelCase__						 =  True






       def 							__A (   self     ):
              _UpperCAmelCase     =     MPNetModelTester(self     )
              _UpperCAmelCase     =     ConfigTester(self    ,  config_class=a__    ,  hidden_size=37     )






       def 							__A (   self     ):
              self.config_tester.run_common_tests()






       def 							__A (   self     ):
              _UpperCAmelCase     =     self.model_tester.prepare_config_and_inputs()
              self.model_tester.create_and_check_mpnet_model(*a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     self.model_tester.prepare_config_and_inputs()
              self.model_tester.create_and_check_mpnet_for_sequence_classification(*a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     self.model_tester.prepare_config_and_inputs()
              self.model_tester.create_and_check_mpnet_for_multiple_choice(*a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     self.model_tester.prepare_config_and_inputs()
              self.model_tester.create_and_check_mpnet_for_token_classification(*a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     self.model_tester.prepare_config_and_inputs()
              self.model_tester.create_and_check_mpnet_for_question_answering(*a__     )



@require_torch
class 	snake_case					(      unittest.TestCase							):






       @slow
       def 							__A (   self     ):
              _UpperCAmelCase     =     MPNetModel.from_pretrained('microsoft/mpnet-base'     )
              _UpperCAmelCase     =     torch.tensor([[0, 3_45, 2_32, 3_28, 7_40, 1_40, 16_95, 69, 60_78, 15_88, 2]]     )
              _UpperCAmelCase     =     model(a__     )[0]
              _UpperCAmelCase     =     torch.Size((1, 11, 7_68)     )
              self.assertEqual(output.shape    ,  a__     )
              _UpperCAmelCase     =     torch.tensor(
                  [[[-0.0_550, 0.1_943, -0.0_740], [-0.0_562, 0.2_211, -0.0_579], [-0.0_437, 0.3_337, -0.0_641]]]     )
              # compare the actual values for a slice.
              self.assertTrue(torch.allclose(output[:, :3, :3]    ,  a__    ,  atol=1E-4     )     )













"""simple docstring"""






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



class 	lowerCAmelCase					:






       def __init__(   self     ):
              _UpperCAmelCase     =     {}






       def 							__A (   self    ,  a__    ,  a__    ,  a__=1     ):
              if self.graph.get(a__     ):
                     if self.graph[u].count([w, v]     ) == 0:
                            self.graph[u].append([w, v]     )
              else:
                     _UpperCAmelCase     =     [[w, v]]
              if not self.graph.get(a__     ):
                     _UpperCAmelCase     =     []






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






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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              if s == d:
                     return []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s

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

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

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






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






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






       def 							__A (   self    ,  a__     ):
              return len(self.graph[u]     )






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     []

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

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

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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              _UpperCAmelCase     =     time()
              self.dfs(a__    ,  a__     )
              _UpperCAmelCase     =     time()
              return end - begin






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     time()
              self.bfs(a__     )
              _UpperCAmelCase     =     time()
              return end - begin



class 	lowerCAmelCase					:






       def __init__(   self     ):
              _UpperCAmelCase     =     {}






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






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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              if s == d:
                     return []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s

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

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

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






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






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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              _UpperCAmelCase     =     time()
              self.dfs(a__    ,  a__     )
              _UpperCAmelCase     =     time()
              return end - begin






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     time()
              self.bfs(a__     )
              _UpperCAmelCase     =     time()
              return end - begin






