


import logging

import torch
from torch import nn
from torch.nn import CrossEntropyLoss, MSELoss

from transformers.file_utils import add_start_docstrings, add_start_docstrings_to_model_forward
from transformers.models.bert.modeling_bert import (
    BERT_INPUTS_DOCSTRING,
    BERT_START_DOCSTRING,
    BertEncoder,
    BertModel,
    BertPreTrainedModel,
)


__lowerCAmelCase     							=			logging.getLogger(__name__)


class  __SCREAMING_SNAKE_CASE       (						__a):


     def 							UpperCAmelCase__  (			self      :		Any       ,  __UpperCamelCase      :		List[str]       ,  __UpperCamelCase      :		Dict       ,  __UpperCamelCase      :		int=None       ,  __UpperCamelCase      :		Dict=None ):
       _UpperCAmelCase												=     self.layer[current_layer](_lowerCamelCase       ,  _lowerCamelCase       ,  head_mask[current_layer] )

       _UpperCAmelCase												=     layer_outputs[0]

       return hidden_states





@add_start_docstrings(
    """The bare Bert Model transformer with PABEE outputting raw hidden-states without any specific head on top."""  ,     __a  ,     )
class  __SCREAMING_SNAKE_CASE       (						__a):


     def __init__(			self      :		Any       ,  __UpperCamelCase      :		Any ):
       super().__init__(_lowerCamelCase )

       _UpperCAmelCase												=     BertEncoderWithPabee(_lowerCamelCase )

       self.init_weights()
       _UpperCAmelCase												=     0
       _UpperCAmelCase												=     0
       _UpperCAmelCase												=     0

       _UpperCAmelCase												=     0


     def 							UpperCAmelCase__  (			self      :		int       ,  __UpperCamelCase      :		List[Any] ):
       _UpperCAmelCase												=     threshold


     def 							UpperCAmelCase__  (			self      :		Any       ,  __UpperCamelCase      :		Optional[Any] ):
       _UpperCAmelCase												=     patience


     def 							UpperCAmelCase__  (			self      :		Optional[Any] ):
       _UpperCAmelCase												=     0
       _UpperCAmelCase												=     0


     def 							UpperCAmelCase__  (			self      :		List[str] ):
       _UpperCAmelCase												=     self.inference_layers_num / self.inference_instances_num
       _UpperCAmelCase												=     (
           F'''*** Patience = {self.patience} Avg. Inference Layers = {avg_inf_layers:.2f} Speed Up ='''
           F''' {1 - avg_inf_layers / self.config.num_hidden_layers:.2f} ***'''
       )
       print(_lowerCamelCase )



     @add_start_docstrings_to_model_forward(_lowerCamelCase )
     def 							UpperCAmelCase__  (			self      :		List[Any]       ,  __UpperCamelCase      :		List[Any]=None       ,  __UpperCamelCase      :		Optional[int]=None       ,  __UpperCamelCase      :		Optional[Any]=None       ,  __UpperCamelCase      :		str=None       ,  __UpperCamelCase      :		Dict=None       ,  __UpperCamelCase      :		Optional[int]=None       ,  __UpperCamelCase      :		List[str]=None       ,  __UpperCamelCase      :		List[Any]=None       ,  __UpperCamelCase      :		Union[str, Any]=None       ,  __UpperCamelCase      :		Tuple=None       ,  __UpperCamelCase      :		Union[str, Any]=False       ,  ):

       if input_ids is not None and inputs_embeds is not None:
         raise ValueError("You cannot specify both input_ids and inputs_embeds at the same time" )
       elif input_ids is not None:
         _UpperCAmelCase												=     input_ids.size()
       elif inputs_embeds is not None:
         _UpperCAmelCase												=     inputs_embeds.size()[:-1]
       else:
         raise ValueError("You have to specify either input_ids or inputs_embeds" )

       _UpperCAmelCase												=     input_ids.device if input_ids is not None else inputs_embeds.device

       if attention_mask is None:
         _UpperCAmelCase												=     torch.ones(_lowerCamelCase       ,  device=_lowerCamelCase )
       if token_type_ids is None:
         _UpperCAmelCase												=     torch.zeros(_lowerCamelCase       ,  dtype=torch.long       ,  device=_lowerCamelCase )

       # We can provide a self-attention mask of dimensions [batch_size, from_seq_length, to_seq_length]
       # ourselves in which case we just need to make it broadcastable to all heads.
       _UpperCAmelCase												=     self.get_extended_attention_mask(_lowerCamelCase       ,  _lowerCamelCase       ,  _lowerCamelCase )

       # If a 2D ou 3D attention mask is provided for the cross-attention
       # we need to make broadcastable to [batch_size, num_heads, seq_length, seq_length]
       if self.config.is_decoder and encoder_hidden_states is not None:
         _UpperCAmelCase						,		_UpperCAmelCase						,		_UpperCAmelCase												=     encoder_hidden_states.size()
         _UpperCAmelCase												=     (encoder_batch_size, encoder_sequence_length)
         if encoder_attention_mask is None:
           _UpperCAmelCase												=     torch.ones(_lowerCamelCase       ,  device=_lowerCamelCase )
         _UpperCAmelCase												=     self.invert_attention_mask(_lowerCamelCase )
       else:
         _UpperCAmelCase												=     None

       # Prepare head mask if needed
       # 1.0 in head_mask indicate we keep the head
       # attention_probs has shape bsz x n_heads x N x N
       # input head_mask has shape [num_heads] or [num_hidden_layers x num_heads]
       # and head_mask is converted to shape [num_hidden_layers x batch x num_heads x seq_length x seq_length]
       _UpperCAmelCase												=     self.get_head_mask(_lowerCamelCase       ,  self.config.num_hidden_layers )

       _UpperCAmelCase												=     self.embeddings(
           input_ids=_lowerCamelCase       ,  position_ids=_lowerCamelCase       ,  token_type_ids=_lowerCamelCase       ,  inputs_embeds=_lowerCamelCase )
       _UpperCAmelCase												=     embedding_output

       if self.training:
         _UpperCAmelCase												=     []
         for i in range(self.config.num_hidden_layers ):
           _UpperCAmelCase												=     self.encoder.adaptive_forward(
               _lowerCamelCase       ,  current_layer=_lowerCamelCase       ,  attention_mask=_lowerCamelCase       ,  head_mask=_lowerCamelCase )

           _UpperCAmelCase												=     self.pooler(_lowerCamelCase )
           _UpperCAmelCase												=     output_layers[i](output_dropout(_lowerCamelCase ) )
           res.append(_lowerCamelCase )
       elif self.patience == 0:  # Use all layers for inference
         _UpperCAmelCase												=     self.encoder(
             _lowerCamelCase       ,  attention_mask=_lowerCamelCase       ,  head_mask=_lowerCamelCase       ,  encoder_hidden_states=_lowerCamelCase       ,  encoder_attention_mask=_lowerCamelCase       ,  )
         _UpperCAmelCase												=     self.pooler(encoder_outputs[0] )
         _UpperCAmelCase												=     [output_layers[self.config.num_hidden_layers - 1](_lowerCamelCase )]
       else:
         _UpperCAmelCase												=     0
         _UpperCAmelCase												=     None
         _UpperCAmelCase												=     0
         for i in range(self.config.num_hidden_layers ):
           calculated_layer_num += 1
           _UpperCAmelCase												=     self.encoder.adaptive_forward(
               _lowerCamelCase       ,  current_layer=_lowerCamelCase       ,  attention_mask=_lowerCamelCase       ,  head_mask=_lowerCamelCase )

           _UpperCAmelCase												=     self.pooler(_lowerCamelCase )
           _UpperCAmelCase												=     output_layers[i](_lowerCamelCase )
           if regression:
             _UpperCAmelCase												=     logits.detach()
             if patient_result is not None:
               _UpperCAmelCase												=     patient_result.detach()
             if (patient_result is not None) and torch.abs(patient_result - labels ) < self.regression_threshold:
               patient_counter += 1
             else:
               _UpperCAmelCase												=     0
           else:
             _UpperCAmelCase												=     logits.detach().argmax(dim=1 )
             if patient_result is not None:
               _UpperCAmelCase												=     patient_result.detach().argmax(dim=1 )
             if (patient_result is not None) and torch.all(labels.eq(_lowerCamelCase ) ):
               patient_counter += 1
             else:
               _UpperCAmelCase												=     0

           _UpperCAmelCase												=     logits
           if patient_counter == self.patience:
             break
         _UpperCAmelCase												=     [patient_result]
         self.inference_layers_num += calculated_layer_num
         self.inference_instances_num += 1

       return res





@add_start_docstrings(
    """Bert Model transformer with PABEE and a sequence classification/regression head on top (a linear layer on top of\n    the pooled output) e.g. for GLUE tasks. """  ,     __a  ,     )
class  __SCREAMING_SNAKE_CASE       (						__a):


     def __init__(			self      :		List[str]       ,  __UpperCamelCase      :		Tuple ):
       super().__init__(_lowerCamelCase )
       _UpperCAmelCase												=     config.num_labels

       _UpperCAmelCase												=     BertModelWithPabee(_lowerCamelCase )
       _UpperCAmelCase												=     nn.Dropout(config.hidden_dropout_prob )
       _UpperCAmelCase												=     nn.ModuleList(
           [nn.Linear(config.hidden_size       ,  self.config.num_labels ) for _ in range(config.num_hidden_layers )] )

       self.init_weights()



     @add_start_docstrings_to_model_forward(_lowerCamelCase )
     def 							UpperCAmelCase__  (			self      :		Dict       ,  __UpperCamelCase      :		Tuple=None       ,  __UpperCamelCase      :		List[str]=None       ,  __UpperCamelCase      :		Any=None       ,  __UpperCamelCase      :		List[Any]=None       ,  __UpperCamelCase      :		Any=None       ,  __UpperCamelCase      :		str=None       ,  __UpperCamelCase      :		Union[str, Any]=None       ,  ):
       _UpperCAmelCase												=     self.bert(
           input_ids=_lowerCamelCase       ,  attention_mask=_lowerCamelCase       ,  token_type_ids=_lowerCamelCase       ,  position_ids=_lowerCamelCase       ,  head_mask=_lowerCamelCase       ,  inputs_embeds=_lowerCamelCase       ,  output_dropout=self.dropout       ,  output_layers=self.classifiers       ,  regression=self.num_labels == 1       ,  )

       _UpperCAmelCase												=     (logits[-1],)

       if labels is not None:
         _UpperCAmelCase												=     None
         _UpperCAmelCase												=     0
         for ix, logits_item in enumerate(_lowerCamelCase ):
           if self.num_labels == 1:
             #  We are doing regression
             _UpperCAmelCase												=     MSELoss()
             _UpperCAmelCase												=     loss_fct(logits_item.view(-1 )       ,  labels.view(-1 ) )
           else:
             _UpperCAmelCase												=     CrossEntropyLoss()
             _UpperCAmelCase												=     loss_fct(logits_item.view(-1       ,  self.num_labels )       ,  labels.view(-1 ) )
           if total_loss is None:
             _UpperCAmelCase												=     loss
           else:
             total_loss += loss * (ix + 1)
           total_weights += ix + 1
         _UpperCAmelCase												=     (total_loss / total_weights,) + outputs

       return outputs




'''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





