





import collections
import inspect
import unittest

from transformers import DonutSwinConfig
from transformers.testing_utils import require_torch, slow, torch_device
from transformers.utils import is_torch_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
    import torch
    from torch import nn

    from transformers import DonutSwinModel
    from transformers.models.donut.modeling_donut_swin import DONUT_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST







class 		_lowerCAmelCase:

  """simple docstring"""







  def __init__(   self    ,							UpperCAmelCase    ,							UpperCAmelCase=13    ,							UpperCAmelCase=32    ,							UpperCAmelCase=2    ,							UpperCAmelCase=3    ,							UpperCAmelCase=16    ,							UpperCAmelCase=[1, 2, 1]    ,							UpperCAmelCase=[2, 2, 4]    ,							UpperCAmelCase=2    ,							UpperCAmelCase=2.0    ,							UpperCAmelCase=True    ,							UpperCAmelCase=0.0    ,							UpperCAmelCase=0.0    ,							UpperCAmelCase=0.1    ,							UpperCAmelCase="gelu"    ,							UpperCAmelCase=False    ,							UpperCAmelCase=True    ,							UpperCAmelCase=0.02    ,							UpperCAmelCase=1e-5    ,							UpperCAmelCase=True    ,							UpperCAmelCase=None    ,							UpperCAmelCase=True    ,							UpperCAmelCase=10    ,							UpperCAmelCase=8    ,							)->   List[Any]:
     __A    =  parent
     __A    =  batch_size
     __A    =  image_size
     __A    =  patch_size
     __A    =  num_channels
     __A    =  embed_dim
     __A    =  depths
     __A    =  num_heads
     __A    =  window_size
     __A    =  mlp_ratio
     __A    =  qkv_bias
     __A    =  hidden_dropout_prob
     __A    =  attention_probs_dropout_prob
     __A    =  drop_path_rate
     __A    =  hidden_act
     __A    =  use_absolute_embeddings
     __A    =  patch_norm
     __A    =  layer_norm_eps
     __A    =  initializer_range
     __A    =  is_training
     __A    =  scope
     __A    =  use_labels
     __A    =  type_sequence_label_size
     __A    =  encoder_stride

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Union[str, Any]:
     __A    =  floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )

     __A    =  None
     if self.use_labels:
        __A    =  ids_tensor([self.batch_size]    ,							self.type_sequence_label_size      )

     __A    =  self.get_config()

     return config, pixel_values, labels

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   List[str]:
     return DonutSwinConfig(
         image_size=self.image_size    ,							patch_size=self.patch_size    ,							num_channels=self.num_channels    ,							embed_dim=self.embed_dim    ,							depths=self.depths    ,							num_heads=self.num_heads    ,							window_size=self.window_size    ,							mlp_ratio=self.mlp_ratio    ,							qkv_bias=self.qkv_bias    ,							hidden_dropout_prob=self.hidden_dropout_prob    ,							attention_probs_dropout_prob=self.attention_probs_dropout_prob    ,							drop_path_rate=self.drop_path_rate    ,							hidden_act=self.hidden_act    ,							use_absolute_embeddings=self.use_absolute_embeddings    ,							path_norm=self.patch_norm    ,							layer_norm_eps=self.layer_norm_eps    ,							initializer_range=self.initializer_range    ,							encoder_stride=self.encoder_stride    ,							)

  def 						SCREAMING_SNAKE_CASE__			(   self    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase      )->   Any:
     __A    =  DonutSwinModel(config=UpperCAmelCase      )
     model.to(UpperCAmelCase      )
     model.eval()
     __A    =  model(UpperCAmelCase      )

     __A    =  ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths      ) - 1))
     __A    =  int(config.embed_dim * 2 ** (len(config.depths      ) - 1)      )

     self.parent.assertEqual(result.last_hidden_state.shape    ,							(self.batch_size, expected_seq_len, expected_dim)      )





  def 						SCREAMING_SNAKE_CASE__			(   self      )->   List[Any]:
     __A    =  self.prepare_config_and_inputs()
     (
         (
         __A
     )   ,		(
         __A
     )   ,		(
         __A
     )   ,		
     )    =  config_and_inputs
     __A    =  {'''pixel_values''': pixel_values}
     return config, inputs_dict







@require_torch
class 		_lowerCAmelCase(		_a						,       _a						,       unittest.TestCase):

  """simple docstring"""







  lowerCamelCase__     	=       (DonutSwinModel,) if is_torch_available() else ()
  lowerCamelCase__     	=       {'''feature-extraction''': DonutSwinModel} if is_torch_available() else {}
  lowerCamelCase__     	=       True

  lowerCamelCase__     	=       False
  lowerCamelCase__     	=       False
  lowerCamelCase__     	=       False

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Union[str, Any]:
     __A    =  DonutSwinModelTester(self      )
     __A    =  ConfigTester(self    ,							config_class=UpperCAmelCase    ,							embed_dim=37      )

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Optional[int]:
     self.create_and_test_config_common_properties()
     self.config_tester.create_and_test_config_to_json_string()
     self.config_tester.create_and_test_config_to_json_file()
     self.config_tester.create_and_test_config_from_and_save_pretrained()
     self.config_tester.create_and_test_config_with_num_labels()
     self.config_tester.check_config_can_be_init_without_params()
     self.config_tester.check_config_arguments_init()

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   str:
     return

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   str:
     __A    =  self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_model(*UpperCAmelCase      )

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Tuple:
     # DonutSwin does not use inputs_embeds
     pass

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Union[str, Any]:
     __A   ,		__A    =  self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
        __A    =  model_class(UpperCAmelCase      )
        self.assertIsInstance(model.get_input_embeddings()    ,							(nn.Module)      )
        __A    =  model.get_output_embeddings()
        self.assertTrue(x is None or isinstance(UpperCAmelCase    ,							nn.Linear      )      )

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   List[str]:
     __A   ,		__A    =  self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
        __A    =  model_class(UpperCAmelCase      )
        __A    =  inspect.signature(model.forward      )
        # signature.parameters is an OrderedDict => so arg_names order is deterministic
        __A    =  [*signature.parameters.keys()]

        __A    =  ['''pixel_values''']
        self.assertListEqual(arg_names[:1]    ,							UpperCAmelCase      )

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Union[str, Any]:
     __A   ,		__A    =  self.model_tester.prepare_config_and_inputs_for_common()
     __A    =  True

     for model_class in self.all_model_classes:
        __A    =  True
        __A    =  False
        __A    =  True
        __A    =  model_class(UpperCAmelCase      )
        model.to(UpperCAmelCase      )
        model.eval()
        with torch.no_grad():
           __A    =  model(**self._prepare_for_class(UpperCAmelCase    ,							UpperCAmelCase      )      )
        __A    =  outputs.attentions
        __A    =  len(self.model_tester.depths      )
        self.assertEqual(len(UpperCAmelCase      )    ,							UpperCAmelCase      )

        # check that output_attentions also work using config
        del inputs_dict["output_attentions"]
        __A    =  True
        __A    =  config.window_size**2
        __A    =  model_class(UpperCAmelCase      )
        model.to(UpperCAmelCase      )
        model.eval()
        with torch.no_grad():
           __A    =  model(**self._prepare_for_class(UpperCAmelCase    ,							UpperCAmelCase      )      )
        __A    =  outputs.attentions
        self.assertEqual(len(UpperCAmelCase      )    ,							UpperCAmelCase      )

        self.assertListEqual(
            list(attentions[0].shape[-3:]      )    ,							[self.model_tester.num_heads[0], window_size_squared, window_size_squared]    ,							)
        __A    =  len(UpperCAmelCase      )

        # Check attention is always last and order is fine
        __A    =  True
        __A    =  True
        __A    =  model_class(UpperCAmelCase      )
        model.to(UpperCAmelCase      )
        model.eval()
        with torch.no_grad():
           __A    =  model(**self._prepare_for_class(UpperCAmelCase    ,							UpperCAmelCase      )      )

        if hasattr(self.model_tester    ,							'''num_hidden_states_types'''      ):
           __A    =  self.model_tester.num_hidden_states_types
        else:
           # also another +1 for reshaped_hidden_states
           __A    =  2
        self.assertEqual(out_len + added_hidden_states    ,							len(UpperCAmelCase      )      )

        __A    =  outputs.attentions

        self.assertEqual(len(UpperCAmelCase      )    ,							UpperCAmelCase      )

        self.assertListEqual(
            list(self_attentions[0].shape[-3:]      )    ,							[self.model_tester.num_heads[0], window_size_squared, window_size_squared]    ,							)

  def 						SCREAMING_SNAKE_CASE__			(   self    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase      )->   Tuple:
     __A    =  model_class(UpperCAmelCase      )
     model.to(UpperCAmelCase      )
     model.eval()

     with torch.no_grad():
        __A    =  model(**self._prepare_for_class(UpperCAmelCase    ,							UpperCAmelCase      )      )

     __A    =  outputs.hidden_states

     __A    =  getattr(
         self.model_tester    ,							'''expected_num_hidden_layers'''    ,							len(self.model_tester.depths      ) + 1      )
     self.assertEqual(len(UpperCAmelCase      )    ,							UpperCAmelCase      )

     # DonutSwin has a different seq_length
     __A    =  (
         config.patch_size
         if isinstance(config.patch_size    ,							collections.abc.Iterable      )
         else (config.patch_size, config.patch_size)
     )

     __A    =  (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

     self.assertListEqual(
         list(hidden_states[0].shape[-2:]      )    ,							[num_patches, self.model_tester.embed_dim]    ,							)

     __A    =  outputs.reshaped_hidden_states
     self.assertEqual(len(UpperCAmelCase      )    ,							UpperCAmelCase      )

     __A   ,		__A   ,		__A   ,		__A    =  reshaped_hidden_states[0].shape
     __A    =  (
         reshaped_hidden_states[0].view(UpperCAmelCase    ,							UpperCAmelCase    ,							height * width      ).permute(0    ,							2    ,							1      )
     )
     self.assertListEqual(
         list(reshaped_hidden_states.shape[-2:]      )    ,							[num_patches, self.model_tester.embed_dim]    ,							)

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Dict:
     __A   ,		__A    =  self.model_tester.prepare_config_and_inputs_for_common()

     __A    =  (
         self.model_tester.image_size
         if isinstance(self.model_tester.image_size    ,							collections.abc.Iterable      )
         else (self.model_tester.image_size, self.model_tester.image_size)
     )

     for model_class in self.all_model_classes:
        __A    =  True
        self.check_hidden_states_output(UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase      )

        # check that output_hidden_states also work using config
        del inputs_dict["output_hidden_states"]
        __A    =  True

        self.check_hidden_states_output(UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase      )

  def 						SCREAMING_SNAKE_CASE__			(   self      )->   str:
     __A   ,		__A    =  self.model_tester.prepare_config_and_inputs_for_common()
     __A    =  3

     __A    =  (
         self.model_tester.image_size
         if isinstance(self.model_tester.image_size    ,							collections.abc.Iterable      )
         else (self.model_tester.image_size, self.model_tester.image_size)
     )
     __A    =  (
         config.patch_size
         if isinstance(config.patch_size    ,							collections.abc.Iterable      )
         else (config.patch_size, config.patch_size)
     )

     __A    =  image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
     __A    =  image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

     for model_class in self.all_model_classes:
        __A    =  True
        self.check_hidden_states_output(UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							(padded_height, padded_width)      )

        # check that output_hidden_states also work using config
        del inputs_dict["output_hidden_states"]
        __A    =  True
        self.check_hidden_states_output(UpperCAmelCase    ,							UpperCAmelCase    ,							UpperCAmelCase    ,							(padded_height, padded_width)      )

  @slow
  def 						SCREAMING_SNAKE_CASE__			(   self      )->   int:
     for model_name in DONUT_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
        __A    =  DonutSwinModel.from_pretrained(UpperCAmelCase      )
        self.assertIsNotNone(UpperCAmelCase      )





  def 						SCREAMING_SNAKE_CASE__			(   self      )->   Any:
     __A   ,		__A    =  self.model_tester.prepare_config_and_inputs_for_common()

     __A    =  _config_zero_init(UpperCAmelCase      )
     for model_class in self.all_model_classes:
        __A    =  model_class(config=UpperCAmelCase      )
        for name, param in model.named_parameters():
           if "embeddings" not in name and param.requires_grad:
              self.assertIn(
                  ((param.data.mean() * 1e9).round() / 1e9).item()    ,							[0.0, 1.0]    ,							msg=f"Parameter {name} of model {model_class} seems not properly initialized"    ,							)








from collections import deque
def  __UpperCamelCase    (						snake_case      )    ->		List[str]:


   '''simple docstring'''







   return input(snake_case      ).strip().split(''' '''      )
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		dict[int, list[int]]:


   '''simple docstring'''







   __A    =  {}
   for i in range(snake_case      ):
      __A    =  []

   for e in range(snake_case      ):
      __A   ,		__A    =  (int(snake_case      ) for i in _input(F"Edge {e + 1}: <node1> <node2> "      ))
      graph[x].append(snake_case      )
   return graph
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		dict[int, list[int]]:


   '''simple docstring'''







   __A    =  {}
   for i in range(snake_case      ):
      __A    =  []

   for e in range(snake_case      ):
      __A   ,		__A    =  (int(snake_case      ) for i in _input(F"Edge {e + 1}: <node1> <node2> "      ))
      graph[x].append(snake_case      )
      graph[y].append(snake_case      )
   return graph
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		dict[int, list[tuple[int, int]]]:


   '''simple docstring'''







   __A    =  {}
   for i in range(snake_case      ):
      __A    =  []

   for e in range(snake_case      ):
      __A   ,		__A   ,		__A    =  (int(snake_case      ) for i in _input(F"Edge {e + 1}: <node1> <node2> <weight> "      ))
      graph[x].append((y, w)      )
      graph[y].append((x, w)      )
   return graph


if __name__ == "__main__":
    _UpperCamelCase       ,    _UpperCamelCase       :				List[Any]           =			(int(i) for i in _input("""Number of nodes and edges: """))

    _UpperCamelCase       :				int           =			int(
        _input(
            """Press 1 or 2 or 3 \n"""
            """1. Unweighted directed \n"""
            """2. Unweighted undirected \n"""
            """3. Weighted undirected \n"""
        )[0]
    )

    _UpperCamelCase       :				Optional[Any]           =			{
        1: initialize_unweighted_directed_graph,
        2: initialize_unweighted_undirected_graph,
        3: initialize_weighted_undirected_graph,
    }[graph_choice](n, m)
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		int:


   '''simple docstring'''







   __A   ,		__A    =  {s}, [s]
   print(snake_case      )
   while _s:
      __A    =  0
      for i in g[_s[-1]]:
         if i not in vis:
            _s.append(snake_case      )
            vis.add(snake_case      )
            __A    =  1
            print(snake_case      )
            break
      if not flag:
         _s.pop()
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		Dict:


   '''simple docstring'''







   __A   ,		__A    =  {s}, deque([s]      )
   print(snake_case      )
   while q:
      __A    =  q.popleft()
      for v in g[u]:
         if v not in vis:
            vis.add(snake_case      )
            q.append(snake_case      )
            print(snake_case      )
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		List[Any]:


   '''simple docstring'''







   __A   ,		__A   ,		__A    =  {s: 0}, set(), {s: 0}
   while True:
      if len(snake_case      ) == len(snake_case      ) - 1:
         break
      __A    =  1_0_0_0_0_0
      for i in dist:
         if i not in known and dist[i] < mini:
            __A    =  dist[i]
            __A    =  i
      known.add(snake_case      )
      for v in g[u]:
         if v[0] not in known and dist[u] + v[1] < dist.get(v[0]							,			1_0_0_0_0_0      ):
            __A    =  dist[u] + v[1]
            __A    =  u
   for i in dist:
      if i != s:
         print(dist[i]      )
def  __UpperCamelCase    (						snake_case							,			snake_case=None							,			snake_case=None      )    ->		Any:


   '''simple docstring'''







   if q is None:
      __A    =  [1]
   if ind is None:
      __A    =  [0] * (len(snake_case      ) + 1)  # SInce oth Index is ignored
      for u in g:
         for v in g[u]:
            ind[v] += 1
      __A    =  deque()
      for i in g:
         if ind[i] == 0:
            q.append(snake_case      )
   if len(snake_case      ) == 0:
      return
   __A    =  q.popleft()
   print(snake_case      )
   for w in g[v]:
      ind[w] -= 1
      if ind[w] == 0:
         q.append(snake_case      )
   topo(snake_case							,			snake_case							,			snake_case      )
def  __UpperCamelCase    (						)    ->		Any:


   '''simple docstring'''







   __A    =  input().strip()
   __A    =  []
   for _ in range(snake_case      ):
      a.append(map(snake_case							,			input().strip().split()      )      )
   return a, n
def  __UpperCamelCase    (						snake_case      )    ->		List[Any]:


   '''simple docstring'''







   ((__A)   ,		(__A))    =  a_and_n
   __A    =  list(snake_case      )
   __A    =  [[0] * n for i in range(snake_case      )]
   for k in range(snake_case      ):
      for i in range(snake_case      ):
         for j in range(snake_case      ):
            if dist[i][j] > dist[i][k] + dist[k][j]:
               __A    =  dist[i][k] + dist[k][j]
               __A    =  k
   print(snake_case      )
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		Dict:


   '''simple docstring'''







   __A   ,		__A   ,		__A    =  {s: 0}, set(), {s: 0}
   while True:
      if len(snake_case      ) == len(snake_case      ) - 1:
         break
      __A    =  1_0_0_0_0_0
      for i in dist:
         if i not in known and dist[i] < mini:
            __A    =  dist[i]
            __A    =  i
      known.add(snake_case      )
      for v in g[u]:
         if v[0] not in known and v[1] < dist.get(v[0]							,			1_0_0_0_0_0      ):
            __A    =  v[1]
            __A    =  u
   return dist
def  __UpperCamelCase    (						)    ->		List[str]:


   '''simple docstring'''







   __A   ,		__A    =  map(snake_case							,			input().split(''' '''      )      )
   __A    =  []
   for _ in range(snake_case      ):
      edges.append(map(snake_case							,			input().split(''' '''      )      )      )
   return edges, n
def  __UpperCamelCase    (						snake_case      )    ->		int:


   '''simple docstring'''







   ((__A)   ,		(__A))    =  e_and_n
   e.sort(reverse=snake_case							,			key=lambda snake_case      : x[2]      )
   __A    =  [{i} for i in range(1							,			n + 1      )]
   while True:
      if len(snake_case      ) == 1:
         break
      print(snake_case      )
      __A    =  e.pop()
      for i in range(len(snake_case      )      ):
         if x[0] in s[i]:
            break
      for j in range(len(snake_case      )      ):
         if x[1] in s[j]:
            if i == j:
               break
            s[j].update(s[i]      )
            s.pop(snake_case      )
            break
def  __UpperCamelCase    (						snake_case      )    ->		Tuple:


   '''simple docstring'''







   __A    =  []
   for node in graph:
      if not graph[node]:
         isolated.append(snake_case      )
   return isolated

