'''simple docstring'''

from __future__ import annotations

import copy
import inspect
import unittest

import numpy as np

from transformers import is_tf_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_tf, slow
from transformers.utils import cached_property

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
 import tensorflow as tf

 from transformers import (
     TF_LAYOUTLMV3_PRETRAINED_MODEL_ARCHIVE_LIST,
     TF_MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
     TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
     TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
     TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
     LayoutLMvaConfig,
     TFLayoutLMvaForQuestionAnswering,
     TFLayoutLMvaForSequenceClassification,
     TFLayoutLMvaForTokenClassification,
     TFLayoutLMvaModel,
 )

if is_vision_available():
 from PIL import Image

 from transformers import LayoutLMvaImageProcessor


class     __UpperCAmelCase       :





  def __init__(	self    ,     _lowerCamelCase    ,     _lowerCamelCase=2    ,     _lowerCamelCase=3    ,     _lowerCamelCase=4    ,     _lowerCamelCase=2    ,     _lowerCamelCase=7    ,     _lowerCamelCase=True    ,     _lowerCamelCase=True    ,     _lowerCamelCase=True    ,     _lowerCamelCase=True    ,     _lowerCamelCase=99    ,     _lowerCamelCase=36    ,     _lowerCamelCase=2    ,     _lowerCamelCase=4    ,     _lowerCamelCase=37    ,     _lowerCamelCase="gelu"    ,     _lowerCamelCase=0.1    ,     _lowerCamelCase=0.1    ,     _lowerCamelCase=512    ,     _lowerCamelCase=16    ,     _lowerCamelCase=2    ,     _lowerCamelCase=0.02    ,     _lowerCamelCase=6    ,     _lowerCamelCase=6    ,     _lowerCamelCase=3    ,     _lowerCamelCase=4    ,     _lowerCamelCase=None    ,     _lowerCamelCase=1000    ,     ):
     lowerCAmelCase_			=      parent
     lowerCAmelCase_			=      batch_size
     lowerCAmelCase_			=      num_channels
     lowerCAmelCase_			=      image_size
     lowerCAmelCase_			=      patch_size
     lowerCAmelCase_			=      is_training
     lowerCAmelCase_			=      use_input_mask
     lowerCAmelCase_			=      use_token_type_ids
     lowerCAmelCase_			=      use_labels
     lowerCAmelCase_			=      vocab_size
     lowerCAmelCase_			=      hidden_size
     lowerCAmelCase_			=      num_hidden_layers
     lowerCAmelCase_			=      num_attention_heads
     lowerCAmelCase_			=      intermediate_size
     lowerCAmelCase_			=      hidden_act
     lowerCAmelCase_			=      hidden_dropout_prob
     lowerCAmelCase_			=      attention_probs_dropout_prob
     lowerCAmelCase_			=      max_position_embeddings
     lowerCAmelCase_			=      type_vocab_size
     lowerCAmelCase_			=      type_sequence_label_size
     lowerCAmelCase_			=      initializer_range
     lowerCAmelCase_			=      coordinate_size
     lowerCAmelCase_			=      shape_size
     lowerCAmelCase_			=      num_labels
     lowerCAmelCase_			=      num_choices
     lowerCAmelCase_			=      scope
     lowerCAmelCase_			=      range_bbox

     # LayoutLMv3's sequence length equals the number of text tokens + number of patches + 1 (we add 1 for the CLS token)
     lowerCAmelCase_			=      text_seq_length
     lowerCAmelCase_			=      (image_size // patch_size) ** 2 + 1
     lowerCAmelCase_			=      self.text_seq_length + self.image_seq_length





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      ids_tensor([self.batch_size, self.text_seq_length]    ,     self.vocab_size )

     lowerCAmelCase_			=      ids_tensor([self.batch_size, self.text_seq_length, 4]    ,     self.range_bbox )
     lowerCAmelCase_			=      bbox.numpy()
     # Ensure that bbox is legal
     for i in range(bbox.shape[0] ):
        for j in range(bbox.shape[1] ):
           if bbox[i, j, 3] < bbox[i, j, 1]:
              lowerCAmelCase_			=      bbox[i, j, 3]
              lowerCAmelCase_			=      bbox[i, j, 1]
              lowerCAmelCase_			=      tmp_coordinate
           if bbox[i, j, 2] < bbox[i, j, 0]:
              lowerCAmelCase_			=      bbox[i, j, 2]
              lowerCAmelCase_			=      bbox[i, j, 0]
              lowerCAmelCase_			=      tmp_coordinate
     lowerCAmelCase_			=      tf.constant(_lowerCamelCase )

     lowerCAmelCase_			=      floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size] )

     lowerCAmelCase_			=      None
     if self.use_input_mask:
        lowerCAmelCase_			=      random_attention_mask([self.batch_size, self.text_seq_length] )

     lowerCAmelCase_			=      None
     if self.use_token_type_ids:
        lowerCAmelCase_			=      ids_tensor([self.batch_size, self.text_seq_length]    ,     self.type_vocab_size )

     lowerCAmelCase_			=      None
     lowerCAmelCase_			=      None
     if self.use_labels:
        lowerCAmelCase_			=      ids_tensor([self.batch_size]    ,     self.type_sequence_label_size )
        lowerCAmelCase_			=      ids_tensor([self.batch_size, self.text_seq_length]    ,     self.num_labels )

     lowerCAmelCase_			=      LayoutLMvaConfig(
         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    ,     type_vocab_size=self.type_vocab_size    ,     initializer_range=self.initializer_range    ,     coordinate_size=self.coordinate_size    ,     shape_size=self.shape_size    ,     input_size=self.image_size    ,     patch_size=self.patch_size    ,     )

     return config, input_ids, bbox, pixel_values, token_type_ids, input_mask, sequence_labels, token_labels





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      TFLayoutLMvaModel(config=_lowerCamelCase )

     # text + image
     lowerCAmelCase_			=      model(_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     training=_lowerCamelCase )
     lowerCAmelCase_			=      model(
         _lowerCamelCase    ,     bbox=_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     attention_mask=_lowerCamelCase    ,     token_type_ids=_lowerCamelCase    ,     training=_lowerCamelCase    ,     )
     lowerCAmelCase_			=      model(_lowerCamelCase    ,     bbox=_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     training=_lowerCamelCase )

     self.parent.assertEqual(result.last_hidden_state.shape    ,     (self.batch_size, self.seq_length, self.hidden_size) )

     # text only
     lowerCAmelCase_			=      model(_lowerCamelCase    ,     training=_lowerCamelCase )
     self.parent.assertEqual(
         result.last_hidden_state.shape    ,     (self.batch_size, self.text_seq_length, self.hidden_size) )

     # image only
     lowerCAmelCase_			=      model({'''pixel_values''': pixel_values}    ,     training=_lowerCamelCase )
     self.parent.assertEqual(
         result.last_hidden_state.shape    ,     (self.batch_size, self.image_seq_length, self.hidden_size) )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      self.num_labels
     lowerCAmelCase_			=      TFLayoutLMvaForSequenceClassification(config=_lowerCamelCase )
     lowerCAmelCase_			=      model(
         _lowerCamelCase    ,     bbox=_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     attention_mask=_lowerCamelCase    ,     token_type_ids=_lowerCamelCase    ,     labels=_lowerCamelCase    ,     training=_lowerCamelCase    ,     )
     self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.num_labels) )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      self.num_labels
     lowerCAmelCase_			=      TFLayoutLMvaForTokenClassification(config=_lowerCamelCase )
     lowerCAmelCase_			=      model(
         _lowerCamelCase    ,     bbox=_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     attention_mask=_lowerCamelCase    ,     token_type_ids=_lowerCamelCase    ,     labels=_lowerCamelCase    ,     training=_lowerCamelCase    ,     )
     self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.text_seq_length, self.num_labels) )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      2
     lowerCAmelCase_			=      TFLayoutLMvaForQuestionAnswering(config=_lowerCamelCase )
     lowerCAmelCase_			=      model(
         _lowerCamelCase    ,     bbox=_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     attention_mask=_lowerCamelCase    ,     token_type_ids=_lowerCamelCase    ,     start_positions=_lowerCamelCase    ,     end_positions=_lowerCamelCase    ,     training=_lowerCamelCase    ,     )
     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 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      self.prepare_config_and_inputs()
     ((lowerCAmelCase_)	,(lowerCAmelCase_)	,(lowerCAmelCase_)	,(lowerCAmelCase_)	,(lowerCAmelCase_)	,(lowerCAmelCase_)	,(lowerCAmelCase_)	,(lowerCAmelCase_))			=      config_and_inputs
     lowerCAmelCase_			=      {
         '''input_ids''': input_ids,
         '''bbox''': bbox,
         '''pixel_values''': pixel_values,
         '''token_type_ids''': token_type_ids,
         '''attention_mask''': input_mask,
     }
     return config, inputs_dict






@require_tf
class     __UpperCAmelCase       ( __a						,       __a						,       unittest.TestCase		):
  __A :				Tuple											= (
      (
          TFLayoutLMvaModel,
          TFLayoutLMvaForQuestionAnswering,
          TFLayoutLMvaForSequenceClassification,
          TFLayoutLMvaForTokenClassification,
      )
      if is_tf_available()
      else ()
  )
  __A :				Optional[Any]											= (
      {'document-question-answering': TFLayoutLMvaForQuestionAnswering, 'feature-extraction': TFLayoutLMvaModel}
      if is_tf_available()
      else {}
  )

  __A :				Union[str, Any]											= False
  __A :				Optional[Any]											= False
  __A :				Optional[Any]											= False





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     return True





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=False ):
     lowerCAmelCase_			=      copy.deepcopy(_lowerCamelCase )

     if model_class in get_values(_lowerCamelCase ):
        lowerCAmelCase_			=      {
            k: tf.tile(tf.expand_dims(_lowerCamelCase    ,     1 )    ,     (1, self.model_tester.num_choices) + (1,) * (v.ndim - 1) )
            if isinstance(_lowerCamelCase    ,     tf.Tensor ) and v.ndim > 0
            else v
            for k, v in inputs_dict.items()
        }

     if return_labels:
        if model_class in get_values(_lowerCamelCase ):
           lowerCAmelCase_			=      tf.ones(self.model_tester.batch_size    ,     dtype=tf.intaa )
        elif model_class in get_values(_lowerCamelCase ):
           lowerCAmelCase_			=      tf.zeros(self.model_tester.batch_size    ,     dtype=tf.intaa )
           lowerCAmelCase_			=      tf.zeros(self.model_tester.batch_size    ,     dtype=tf.intaa )
        elif model_class in get_values(_lowerCamelCase ):
           lowerCAmelCase_			=      tf.zeros(self.model_tester.batch_size    ,     dtype=tf.intaa )
        elif model_class in get_values(_lowerCamelCase ):
           lowerCAmelCase_			=      tf.zeros(
               (self.model_tester.batch_size, self.model_tester.text_seq_length)    ,     dtype=tf.intaa )

     return inputs_dict





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      TFLayoutLMvaModelTester(self )
     lowerCAmelCase_			=      ConfigTester(self    ,     config_class=_lowerCamelCase    ,     hidden_size=37 )





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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_	,lowerCAmelCase_			=      self.model_tester.prepare_config_and_inputs_for_common()
     for model_class in self.all_model_classes:
        lowerCAmelCase_			=      model_class(_lowerCamelCase )
        if getattr(_lowerCamelCase    ,     '''hf_compute_loss'''    ,     _lowerCamelCase ):
           # The number of elements in the loss should be the same as the number of elements in the label
           lowerCAmelCase_			=      self._prepare_for_class(inputs_dict.copy()    ,     _lowerCamelCase    ,     return_labels=_lowerCamelCase )
           lowerCAmelCase_			=      prepared_for_class[
               sorted(prepared_for_class.keys() - inputs_dict.keys()    ,     reverse=_lowerCamelCase )[0]
           ]
           lowerCAmelCase_			=      added_label.shape.as_list()[:1]

           # Test that model correctly compute the loss with kwargs
           lowerCAmelCase_			=      self._prepare_for_class(inputs_dict.copy()    ,     _lowerCamelCase    ,     return_labels=_lowerCamelCase )
           lowerCAmelCase_			=      prepared_for_class.pop('''input_ids''' )

           lowerCAmelCase_			=      model(_lowerCamelCase    ,     **_lowerCamelCase )[0]
           self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1] )

           # Test that model correctly compute the loss when we mask some positions
           lowerCAmelCase_			=      self._prepare_for_class(inputs_dict.copy()    ,     _lowerCamelCase    ,     return_labels=_lowerCamelCase )
           lowerCAmelCase_			=      prepared_for_class.pop('''input_ids''' )
           if "labels" in prepared_for_class:
              lowerCAmelCase_			=      prepared_for_class['''labels'''].numpy()
              if len(labels.shape ) > 1 and labels.shape[1] != 1:
                 lowerCAmelCase_			=      -100
                 lowerCAmelCase_			=      tf.convert_to_tensor(_lowerCamelCase )
                 lowerCAmelCase_			=      model(_lowerCamelCase    ,     **_lowerCamelCase )[0]
                 self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1] )
                 self.assertTrue(not np.any(np.isnan(loss.numpy() ) ) )

                # Test that model correctly compute the loss with a dict
           lowerCAmelCase_			=      self._prepare_for_class(inputs_dict.copy()    ,     _lowerCamelCase    ,     return_labels=_lowerCamelCase )
           lowerCAmelCase_			=      model(_lowerCamelCase )[0]
           self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1] )

           # Test that model correctly compute the loss with a tuple
           lowerCAmelCase_			=      self._prepare_for_class(inputs_dict.copy()    ,     _lowerCamelCase    ,     return_labels=_lowerCamelCase )

           # Get keys that were added with the _prepare_for_class function
           lowerCAmelCase_			=      prepared_for_class.keys() - inputs_dict.keys()
           lowerCAmelCase_			=      inspect.signature(model.call ).parameters
           lowerCAmelCase_			=      list(signature.keys() )

           # Create a dictionary holding the location of the tensors in the tuple
           lowerCAmelCase_			=      {0: '''input_ids'''}
           for label_key in label_keys:
              lowerCAmelCase_			=      signature_names.index(_lowerCamelCase )
              lowerCAmelCase_			=      label_key
           lowerCAmelCase_			=      sorted(tuple_index_mapping.items() )
           # Initialize a list with their default values, update the values and convert to a tuple
           lowerCAmelCase_			=      []

           for name in signature_names:
              if name != "kwargs":
                 list_input.append(signature[name].default )

           for index, value in sorted_tuple_index_mapping:
              lowerCAmelCase_			=      prepared_for_class[value]

           lowerCAmelCase_			=      tuple(_lowerCamelCase )

           # Send to model
           lowerCAmelCase_			=      model(tuple_input[:-1] )[0]

           self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1] )





  def 						UpperCAmelCase_	(	self ):
     (
         (
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,
     )			=      self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_model(_lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )





  def 						UpperCAmelCase_	(	self ):
     (
         (
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,
     )			=      self.model_tester.prepare_config_and_inputs()
     for type in ["absolute", "relative_key", "relative_key_query"]:
        lowerCAmelCase_			=      type
        self.model_tester.create_and_check_model(_lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )





  def 						UpperCAmelCase_	(	self ):
     (
         (
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,
     )			=      self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_sequence_classification(
         _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )





  def 						UpperCAmelCase_	(	self ):
     (
         (
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,
     )			=      self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_token_classification(
         _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )





  def 						UpperCAmelCase_	(	self ):
     (
         (
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,(
         lowerCAmelCase_
     )	,
     )			=      self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_question_answering(
         _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )







  @slow
  def 						UpperCAmelCase_	(	self ):
     for model_name in TF_LAYOUTLMV3_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
        lowerCAmelCase_			=      TFLayoutLMvaModel.from_pretrained(_lowerCamelCase )
        self.assertIsNotNone(_lowerCamelCase )






def snake_case_      (					)			->					Any:
   lowerCAmelCase_			=      Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png''')
   return image






@require_tf
class     __UpperCAmelCase       ( unittest.TestCase		):





  @cached_property
  def 						UpperCAmelCase_	(	self ):
     return LayoutLMvaImageProcessor(apply_ocr=_lowerCamelCase ) if is_vision_available() else None







  @slow
  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      TFLayoutLMvaModel.from_pretrained('''microsoft/layoutlmv3-base''' )

     lowerCAmelCase_			=      self.default_image_processor
     lowerCAmelCase_			=      prepare_img()
     lowerCAmelCase_			=      image_processor(images=_lowerCamelCase    ,     return_tensors='''tf''' ).pixel_values

     lowerCAmelCase_			=      tf.constant([[1, 2]] )
     lowerCAmelCase_			=      tf.expand_dims(tf.constant([[1, 2, 3, 4], [5, 6, 7, 8]] )    ,     axis=0 )

     # forward pass
     lowerCAmelCase_			=      model(input_ids=_lowerCamelCase    ,     bbox=_lowerCamelCase    ,     pixel_values=_lowerCamelCase    ,     training=_lowerCamelCase )

     # verify the logits
     lowerCAmelCase_			=      (1, 199, 768)
     self.assertEqual(outputs.last_hidden_state.shape    ,     _lowerCamelCase )

     lowerCAmelCase_			=      tf.constant(
         [[-0.05_29, 0.36_18, 0.16_32], [-0.15_87, -0.16_67, -0.04_00], [-0.15_57, -0.16_71, -0.05_05]] )

     self.assertTrue(np.allclose(outputs.last_hidden_state[0, :3, :3]    ,     _lowerCamelCase    ,     atol=1E-4 ) )






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





