


import unittest

from transformers import AutoTokenizer, FalconConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
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 (
        FalconForCausalLM,
        FalconForQuestionAnswering,
        FalconForSequenceClassification,
        FalconForTokenClassification,
        FalconModel,
    )



class 	__lowerCamelCase			:







       def __init__(			self: Optional[Any],A_: int,A_: str=3,A_: List[Any]=7,A_: List[str]=True,A_: List[str]=True,A_: Any=False,A_: int=True,A_: str=99,A_: List[str]=32,A_: Optional[Any]=5,A_: Optional[int]=4,A_: List[Any]=37,A_: List[str]="gelu",A_: Tuple=0.1,A_: Any=0.1,A_: str=512,A_: Any=16,A_: List[str]=2,A_: Dict=0.0_2,A_: Tuple=3,A_: Union[str, Any]=4,A_: Union[str, Any]=None,):






            '''simple docstring'''




            __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 		snake_case_	(			self: Optional[Any]					):






            '''simple docstring'''




            __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
            __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, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels







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






            '''simple docstring'''




            return FalconConfig(
                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,is_decoder=A_,initializer_range=self.initializer_range,pad_token_id=1,new_decoder_architecture=A_,)







       def 		snake_case_	(			self: int,A_: Union[str, Any],A_: Union[str, Any],A_: int,A_: Any,A_: Tuple,A_: Any,A_: Tuple					):






            '''simple docstring'''




            __UpperCamelCase =			FalconModel(config=A_					)
            model.to(A_					)
            model.eval()
            __UpperCamelCase =			model(A_,attention_mask=A_					)
            __UpperCamelCase =			model(A_					)
            self.parent.assertEqual(result.last_hidden_state.shape,(self.batch_size, self.seq_length, self.hidden_size)					)







       def 		snake_case_	(			self: Dict,A_: Any,A_: Optional[Any],A_: List[str],A_: str,A_: Optional[Any],A_: Optional[Any],A_: Dict,A_: Optional[Any],A_: str,):






            '''simple docstring'''




            __UpperCamelCase =			True
            __UpperCamelCase =			FalconModel(A_					)
            model.to(A_					)
            model.eval()
            __UpperCamelCase =			model(
                A_,attention_mask=A_,encoder_hidden_states=A_,encoder_attention_mask=A_,)
            __UpperCamelCase =			model(
                A_,attention_mask=A_,encoder_hidden_states=A_,)
            __UpperCamelCase =			model(A_,attention_mask=A_					)
            self.parent.assertEqual(result.last_hidden_state.shape,(self.batch_size, self.seq_length, self.hidden_size)					)







       def 		snake_case_	(			self: Union[str, Any],A_: Union[str, Any],A_: List[str],A_: Tuple,A_: List[Any],A_: Tuple,A_: int,A_: int,A_: Tuple,A_: Tuple,):






            '''simple docstring'''




            __UpperCamelCase =			FalconForCausalLM(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.vocab_size)					)







       def 		snake_case_	(			self: str,A_: int,A_: str,A_: Optional[int],A_: Optional[int],A_: List[str],A_: str,A_: Union[str, Any],A_: Tuple,A_: Dict,):






            '''simple docstring'''




            __UpperCamelCase =			True
            __UpperCamelCase =			True
            __UpperCamelCase =			FalconForCausalLM(config=A_					)
            model.to(A_					)
            model.eval()

            # first forward pass
            __UpperCamelCase =			model(
                A_,attention_mask=A_,encoder_hidden_states=A_,encoder_attention_mask=A_,use_cache=A_,)
            __UpperCamelCase =			outputs.past_key_values

            # create hypothetical multiple next token and extent to next_input_ids
            __UpperCamelCase =			ids_tensor((self.batch_size, 3),config.vocab_size					)
            __UpperCamelCase =			ids_tensor((self.batch_size, 3),vocab_size=2					)

            # append to next input_ids and
            __UpperCamelCase =			torch.cat([input_ids, next_tokens],dim=-1					)
            __UpperCamelCase =			torch.cat([input_mask, next_mask],dim=-1					)

            __UpperCamelCase =			model(
                A_,attention_mask=A_,encoder_hidden_states=A_,encoder_attention_mask=A_,output_hidden_states=A_,)['hidden_states'][0]
            __UpperCamelCase =			model(
                A_,attention_mask=A_,encoder_hidden_states=A_,encoder_attention_mask=A_,past_key_values=A_,output_hidden_states=A_,)['hidden_states'][0]

            # select random slice
            __UpperCamelCase =			ids_tensor((1,),output_from_past.shape[-1]					).item()
            __UpperCamelCase =			output_from_no_past[:, -3:, random_slice_idx].detach()
            __UpperCamelCase =			output_from_past[:, :, random_slice_idx].detach()

            self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]					)

            # test that outputs are equal for slice
            self.parent.assertTrue(torch.allclose(A_,A_,atol=1E-3					)					)







       def 		snake_case_	(			self: List[Any]					):






            '''simple docstring'''




            __UpperCamelCase =			self.prepare_config_and_inputs()
            (
                (
                __UpperCamelCase
            ),    (
                __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 	__lowerCamelCase			(_a				,      _a				,      _a				,      unittest.TestCase						):
       _lowercase											=     (
           (
               FalconModel,
               FalconForCausalLM,
               FalconForSequenceClassification,
               FalconForTokenClassification,
               FalconForQuestionAnswering,
           )
           if is_torch_available()
           else ()
       )
       _lowercase											=     (FalconForCausalLM,) if is_torch_available() else ()
       _lowercase											=     (
           {
               """feature-extraction""": FalconModel,
               """text-classification""": FalconForSequenceClassification,
               """text-generation""": FalconForCausalLM,
               """question-answering""": FalconForQuestionAnswering,
               """token-classification""": FalconForTokenClassification,
               """zero-shot""": FalconForSequenceClassification,
           }
           if is_torch_available()
           else {}
       )
       _lowercase											=     False
       _lowercase											=     False







       def 		snake_case_	(			self: List[str]					):






            '''simple docstring'''




            __UpperCamelCase =			FalconModelTester(self					)
            __UpperCamelCase =			ConfigTester(self,config_class=A_,hidden_size=37					)







       def 		snake_case_	(			self: Dict					):






            '''simple docstring'''




            self.config_tester.run_common_tests()







       def 		snake_case_	(			self: Dict					):






            '''simple docstring'''




            __UpperCamelCase =			self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_model(*A_					)







       def 		snake_case_	(			self: Optional[Any]					):






            '''simple docstring'''




            __UpperCamelCase,    *__UpperCamelCase =			self.model_tester.prepare_config_and_inputs()
            for alibi in [True, False]:
                 __UpperCamelCase =			alibi
                 self.model_tester.create_and_check_model(A_,*A_					)







       def 		snake_case_	(			self: Dict					):






            '''simple docstring'''




            __UpperCamelCase,    __UpperCamelCase =			self.model_tester.prepare_config_and_inputs_for_common()
            __UpperCamelCase =			3
            __UpperCamelCase =			input_dict['input_ids']
            __UpperCamelCase =			input_ids.ne(1					).to(A_					)
            __UpperCamelCase =			ids_tensor([self.model_tester.batch_size],self.model_tester.type_sequence_label_size					)
            __UpperCamelCase =			FalconForSequenceClassification(A_					)
            model.to(A_					)
            model.eval()
            __UpperCamelCase =			model(A_,attention_mask=A_,labels=A_					)
            self.assertEqual(result.logits.shape,(self.model_tester.batch_size, self.model_tester.num_labels)					)







       def 		snake_case_	(			self: int					):






            '''simple docstring'''




            __UpperCamelCase,    __UpperCamelCase =			self.model_tester.prepare_config_and_inputs_for_common()
            __UpperCamelCase =			3
            __UpperCamelCase =			'single_label_classification'
            __UpperCamelCase =			input_dict['input_ids']
            __UpperCamelCase =			input_ids.ne(1					).to(A_					)
            __UpperCamelCase =			ids_tensor([self.model_tester.batch_size],self.model_tester.type_sequence_label_size					)
            __UpperCamelCase =			FalconForSequenceClassification(A_					)
            model.to(A_					)
            model.eval()
            __UpperCamelCase =			model(A_,attention_mask=A_,labels=A_					)
            self.assertEqual(result.logits.shape,(self.model_tester.batch_size, self.model_tester.num_labels)					)







       def 		snake_case_	(			self: List[str]					):






            '''simple docstring'''




            __UpperCamelCase,    __UpperCamelCase =			self.model_tester.prepare_config_and_inputs_for_common()
            __UpperCamelCase =			input_dict['input_ids']
            __UpperCamelCase =			FalconForCausalLM(A_					)
            model.to(A_					)
            model.eval()
            __UpperCamelCase =			model(A_,use_cache=A_					)
            __UpperCamelCase =			input_ids.shape[0]
            __UpperCamelCase =			model._convert_to_rw_cache(result.past_key_values					)
            __UpperCamelCase =			model._convert_cache_to_standard_format(A_,A_					)
            for layer in range(len(A_					)					):
                 for tensor_idx in range(2					):
                      self.assertTrue(rw_cache[layer][tensor_idx].ndim == 3					)
                      self.assertTrue(result.past_key_values[layer][tensor_idx].ndim == 4					)
                      self.assertTrue(
                          torch.all(result.past_key_values[layer][tensor_idx] == standard_cache[layer][tensor_idx]					)					)







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






            '''simple docstring'''




            __UpperCamelCase,    __UpperCamelCase =			self.model_tester.prepare_config_and_inputs_for_common()
            __UpperCamelCase =			3
            __UpperCamelCase =			'multi_label_classification'
            __UpperCamelCase =			input_dict['input_ids']
            __UpperCamelCase =			input_ids.ne(1					).to(A_					)
            __UpperCamelCase =			ids_tensor(
                [self.model_tester.batch_size, config.num_labels],self.model_tester.type_sequence_label_size					).to(torch.float					)
            __UpperCamelCase =			FalconForSequenceClassification(A_					)
            model.to(A_					)
            model.eval()
            __UpperCamelCase =			model(A_,attention_mask=A_,labels=A_					)
            self.assertEqual(result.logits.shape,(self.model_tester.batch_size, self.model_tester.num_labels)					)







       def 		snake_case_	(			self: List[str]					):






            '''simple docstring'''




            for model_class in self.all_generative_model_classes:
                 __UpperCamelCase,    __UpperCamelCase =			self.model_tester.prepare_config_and_inputs_for_common()

                 # If it doesn't support cache, pass the test
                 if not hasattr(A_,'use_cache'					):
                      return

                 __UpperCamelCase =			model_class(A_					).to(A_					)
                 if "use_cache" not in inputs:
                      __UpperCamelCase =			True
                 __UpperCamelCase =			model(**A_					)

                 # If "past_key_values" is not returned, pass the test (e.g. RWKV uses a different cache name and format)
                 if "past_key_values" not in outputs:
                      return

                 __UpperCamelCase =			(
                     getattr(A_,'decoder_layers',A_					)
                     or getattr(A_,'num_decoder_layers',A_					)
                     or config.num_hidden_layers
                 )
                 __UpperCamelCase =			getattr(A_,'num_kv_heads',config.num_attention_heads					)
                 __UpperCamelCase =			getattr(A_,'d_model',config.hidden_size					)
                 __UpperCamelCase =			embed_dim // num_attention_heads

                 __UpperCamelCase =			outputs['past_key_values']
                 self.assertEqual(len(A_					),A_					)

                 __UpperCamelCase,    __UpperCamelCase =			inputs['input_ids'].shape
                 for i in range(A_					):
                      if config.new_decoder_architecture:
                           __UpperCamelCase =			config.num_attention_heads
                      elif config.multi_query:
                           __UpperCamelCase =			1
                      self.assertEqual(len(past_kv[0]					),2					)  # K V for the decoder = 2
                      self.assertEqual(
                          past_kv[i][0].shape,(batch_size, num_attention_heads, seq_length, per_head_embed_dim)					)
                      self.assertEqual(
                          past_kv[i][1].shape,(batch_size, num_attention_heads, seq_length, per_head_embed_dim)					)



@require_torch
class 	__lowerCamelCase			(unittest.TestCase						):







       @slow
       def 		snake_case_	(			self: List[str]					):






            '''simple docstring'''




            __UpperCamelCase =			AutoTokenizer.from_pretrained('Rocketknight1/falcon-rw-1b'					)
            __UpperCamelCase =			FalconForCausalLM.from_pretrained('Rocketknight1/falcon-rw-1b'					)
            model.eval()
            model.to(A_					)
            __UpperCamelCase =			tokenizer('My favorite food is',return_tensors='pt'					).to(A_					)

            __UpperCamelCase =			(
                'My favorite food is pizza. I love it so much that I have a pizza party every year for my birthday.'
            )

            __UpperCamelCase =			model.generate(**A_,do_sample=A_,max_new_tokens=19					)
            __UpperCamelCase =			tokenizer.batch_decode(A_					)[0]

            self.assertEqual(A_,A_					)







       @slow
       def 		snake_case_	(			self: Dict					):






            '''simple docstring'''




            for repo in ["Rocketknight1/tiny-random-falcon-7b", "Rocketknight1/tiny-random-falcon-40b"]:
                 __UpperCamelCase =			AutoTokenizer.from_pretrained(A_					)
                 __UpperCamelCase =			FalconForCausalLM.from_pretrained(A_					)
                 model.eval()
                 model.to(A_					)
                 __UpperCamelCase =			tokenizer('My favorite food is',return_tensors='pt'					).to(A_					)

                 # We just test that these run without errors - the models are randomly initialized
                 # and so the actual text outputs will be garbage
                 model.generate(**A_,do_sample=A_,max_new_tokens=4					)
                 model.generate(**A_,do_sample=A_,max_new_tokens=4					)
                 model.generate(**A_,num_beams=2,max_new_tokens=4					)







       @slow
       def 		snake_case_	(			self: Optional[Any]					):






            '''simple docstring'''




            with torch.no_grad():
                 for repo in [
                     "Rocketknight1/falcon-rw-1b",
                     "Rocketknight1/tiny-random-falcon-7b",
                     "Rocketknight1/tiny-random-falcon-40b",
                 ]:
                      __UpperCamelCase =			AutoTokenizer.from_pretrained(A_					)
                      __UpperCamelCase =			FalconForCausalLM.from_pretrained(A_					)
                      model.eval()
                      model.to(device=A_					)
                      __UpperCamelCase =			tokenizer('My favorite food is',return_tensors='pt'					).to(A_					)

                      # Test results are the same with and without cache
                      __UpperCamelCase =			model.generate(**A_,do_sample=A_,max_new_tokens=20,use_cache=A_					)
                      __UpperCamelCase =			model.generate(**A_,do_sample=A_,max_new_tokens=20,use_cache=A_					)
                      self.assertTrue((outputs_cache - outputs_no_cache).sum().item() == 0					)









"""simple docstring"""
from __future__ import annotations

import os
from collections.abc import Mapping

__UpperCamelCase     :						Optional[Any]						       =  tuple[int, int]







class       a							:



 def __init__(     self				,       _snake_case				,       _snake_case     ):







  """simple docstring"""






  lowerCAmelCase    				= vertices
  lowerCAmelCase    				= {
      (min(_snake_case     ), max(_snake_case     )): weight for edge, weight in edges.items()
  }



 def    UpperCamelCase__  (     self				,       _snake_case				,       _snake_case     ):







  """simple docstring"""






  self.vertices.add(edge[0]     )
  self.vertices.add(edge[1]     )
  lowerCAmelCase    				= weight



 def    UpperCamelCase__  (     self     ):







  """simple docstring"""






  lowerCAmelCase    				= Graph({min(self.vertices     )}				,       {}     )
  lowerCAmelCase    				= 42
  lowerCAmelCase    				= 42
  lowerCAmelCase    				= 42
  lowerCAmelCase    				= 42

  while len(subgraph.vertices     ) < len(self.vertices     ):
   lowerCAmelCase    				= max(self.edges.values()     ) + 1
   for edge, weight in self.edges.items():
    if (edge[0] in subgraph.vertices) ^ (edge[1] in subgraph.vertices):
     if weight < min_weight:
      lowerCAmelCase    				= edge
      lowerCAmelCase    				= weight

   subgraph.add_edge(_snake_case				,       _snake_case     )

  return subgraph


def 		_SCREAMING_SNAKE_CASE			(_UpperCAmelCase					:    str = "p107_network.txt"			):
 lowerCAmelCase    				= os.path.abspath(os.path.dirname(_UpperCAmelCase			)			)
 lowerCAmelCase    				= os.path.join(_UpperCAmelCase  ,     _UpperCAmelCase			)
 lowerCAmelCase    				= {}
 lowerCAmelCase    				= 42
 lowerCAmelCase    				= 42
 lowerCAmelCase    				= 42

 with open(_UpperCAmelCase			) as f:
  lowerCAmelCase    				= f.read().strip().split('\n'			)

 lowerCAmelCase    				= [line.split(','			) for line in data]

 for edgea in range(1  ,     len(_UpperCAmelCase			)			):
  for edgea in range(_UpperCAmelCase			):
   if adjaceny_matrix[edgea][edgea] != "-":
    lowerCAmelCase    				= int(adjaceny_matrix[edgea][edgea]			)

 lowerCAmelCase    				= Graph(set(range(len(_UpperCAmelCase			)			)			)  ,     _UpperCAmelCase			)

 lowerCAmelCase    				= graph.prims_algorithm()

 lowerCAmelCase    				= sum(graph.edges.values()			)
 lowerCAmelCase    				= sum(subgraph.edges.values()			)

 return initial_total - optimal_total


if __name__ == "__main__":
       print(f'''{solution() = }''')





