






from collections import defaultdict
def 					snake_case_						(   lowerCAmelCase_				:  int					):
							__lowercase					:							Tuple			=   1
							__lowercase					:							Tuple			=   True
							for v in tree[start]:
														if v not in visited:
																					ret += dfs(lowerCAmelCase_					)
							if ret % 2 == 0:
														cuts.append(lowerCAmelCase_					)
							return ret
def 					snake_case_						(   ):
							dfs(1					)


if __name__ == "__main__":
	lowerCamelCase      ,lowerCamelCase       :       Optional[int]        =				10, 9
	lowerCamelCase       :       str        =				defaultdict(list)
	lowerCamelCase       :       dict[int, bool]        =				{}
	lowerCamelCase       :       list[int]        =				[]
	lowerCamelCase       :       Optional[Any]        =				0
	lowerCamelCase       :       int        =				[(2, 1), (3, 1), (4, 3), (5, 2), (6, 1), (7, 2), (8, 6), (9, 8), (10, 8)]
	for u, v in edges:
		tree[u].append(v)
		tree[v].append(u)
	even_tree()
	print(len(cuts) - 1)







import inspect
import unittest

from transformers import ConvNextVaConfig
from transformers.models.auto import get_values
from transformers.models.auto.modeling_auto import MODEL_FOR_BACKBONE_MAPPING_NAMES, MODEL_MAPPING_NAMES
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

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


if is_torch_available():
	import torch

	from transformers import ConvNextVaBackbone, ConvNextVaForImageClassification, ConvNextVaModel
	from transformers.models.convnextva.modeling_convnextva import CONVNEXTV2_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
	from PIL import Image

	from transformers import AutoImageProcessor

class 						lowerCAmelCase   :

					'''simple docstring'''

					def __init__(     self :		List[Any]						,   __a :		int						,   __a :		Tuple=13						,   __a :		int=32						,   __a :		List[Any]=3						,   __a :		Dict=4						,   __a :		List[str]=[10, 20, 30, 40]						,   __a :		Any=[2, 2, 3, 2]						,   __a :		List[str]=True						,   __a :		Any=True						,   __a :		Optional[Any]=37						,   __a :		Dict="gelu"						,   __a :		Tuple=10						,   __a :		Dict=0.02						,   __a :		Optional[Any]=["stage2", "stage3", "stage4"]						,   __a :		Optional[int]=[2, 3, 4]						,   __a :		int=None						,   )	->     Optional[Any]:


												"""simple docstring"""

												__lowercase					:							List[str]			=   parent
												__lowercase					:							str			=   batch_size
												__lowercase					:							List[str]			=   image_size
												__lowercase					:							int			=   num_channels
												__lowercase					:							Optional[int]			=   num_stages
												__lowercase					:							str			=   hidden_sizes
												__lowercase					:							Dict			=   depths
												__lowercase					:							List[str]			=   is_training
												__lowercase					:							Optional[Any]			=   use_labels
												__lowercase					:							Optional[Any]			=   intermediate_size
												__lowercase					:							Tuple			=   hidden_act
												__lowercase					:							List[Any]			=   num_labels
												__lowercase					:							Dict			=   initializer_range
												__lowercase					:							List[str]			=   out_features
												__lowercase					:							str			=   out_indices
												__lowercase					:							Optional[Any]			=   scope



					def 					lowerCAmelCase (     self :		List[Any]							)	->     List[Any]:


												"""simple docstring"""

												__lowercase					:							List[Any]			=   floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]							)

												__lowercase					:							Optional[int]			=   None
												if self.use_labels:
																			__lowercase					:							Optional[Any]			=   ids_tensor([self.batch_size]						,   self.num_labels							)

												__lowercase					:							Union[str, Any]			=   self.get_config()

												return config, pixel_values, labels



					def 					lowerCAmelCase (     self :		Union[str, Any]							)	->     str:


												"""simple docstring"""

												return ConvNextVaConfig(
												    num_channels=self.num_channels						,   hidden_sizes=self.hidden_sizes						,   depths=self.depths						,   num_stages=self.num_stages						,   hidden_act=self.hidden_act						,   is_decoder=__a						,   initializer_range=self.initializer_range						,   out_features=self.out_features						,   out_indices=self.out_indices						,   num_labels=self.num_labels						,   )



					def 					lowerCAmelCase (     self :		int						,   __a :		Tuple						,   __a :		Dict						,   __a :		List[str]							)	->     Dict:


												"""simple docstring"""

												__lowercase					:							str			=   ConvNextVaModel(config=__a							)
												model.to(__a							)
												model.eval()
												__lowercase					:							Union[str, Any]			=   model(__a							)
												# expected last hidden states: B, C, H // 32, W // 32
												self.parent.assertEqual(
												    result.last_hidden_state.shape						,   (self.batch_size, self.hidden_sizes[-1], self.image_size // 32, self.image_size // 32)						,   )



					def 					lowerCAmelCase (     self :		Any						,   __a :		Tuple						,   __a :		Any						,   __a :		Union[str, Any]							)	->     Optional[int]:


												"""simple docstring"""

												__lowercase					:							int			=   ConvNextVaForImageClassification(__a							)
												model.to(__a							)
												model.eval()
												__lowercase					:							Union[str, Any]			=   model(__a						,   labels=__a							)
												self.parent.assertEqual(result.logits.shape						,   (self.batch_size, self.num_labels)							)



					def 					lowerCAmelCase (     self :		int						,   __a :		str						,   __a :		Any						,   __a :		Optional[int]							)	->     Dict:


												"""simple docstring"""

												__lowercase					:							Union[str, Any]			=   ConvNextVaBackbone(config=__a							)
												model.to(__a							)
												model.eval()
												__lowercase					:							Dict			=   model(__a							)

												# verify hidden states
												self.parent.assertEqual(len(result.feature_maps							)						,   len(config.out_features							)							)
												self.parent.assertListEqual(list(result.feature_maps[0].shape							)						,   [self.batch_size, self.hidden_sizes[1], 4, 4]							)

												# verify channels
												self.parent.assertEqual(len(model.channels							)						,   len(config.out_features							)							)
												self.parent.assertListEqual(model.channels						,   config.hidden_sizes[1:]							)

												# verify backbone works with out_features=None
												__lowercase					:							List[str]			=   None
												__lowercase					:							str			=   ConvNextVaBackbone(config=__a							)
												model.to(__a							)
												model.eval()
												__lowercase					:							Optional[Any]			=   model(__a							)

												# verify feature maps
												self.parent.assertEqual(len(result.feature_maps							)						,   1							)
												self.parent.assertListEqual(list(result.feature_maps[0].shape							)						,   [self.batch_size, self.hidden_sizes[-1], 1, 1]							)

												# verify channels
												self.parent.assertEqual(len(model.channels							)						,   1							)
												self.parent.assertListEqual(model.channels						,   [config.hidden_sizes[-1]]							)



					def 					lowerCAmelCase (     self :		str							)	->     List[str]:


												"""simple docstring"""

												__lowercase					:							Any			=   self.prepare_config_and_inputs()
												__lowercase	,	__lowercase	,	__lowercase					:							Optional[int]			=   config_and_inputs
												__lowercase					:							List[Any]			=   {"""pixel_values""": pixel_values}
												return config, inputs_dict



					def 					lowerCAmelCase (     self :		Optional[int]							)	->     str:


												"""simple docstring"""

												__lowercase					:							Dict			=   self.prepare_config_and_inputs()
												__lowercase	,	__lowercase	,	__lowercase					:							Optional[Any]			=   config_and_inputs
												__lowercase					:							int			=   {"""pixel_values""": pixel_values, """labels""": labels}
												return config, inputs_dict







@require_torch
class 						lowerCAmelCase   (       __a					,				__a					,				unittest.TestCase	):

					'''simple docstring'''

					_A  :	Any     =					(
					    (
					        ConvNextVaModel,
					        ConvNextVaForImageClassification,
					        ConvNextVaBackbone,
					    )
					    if is_torch_available()
					    else ()
					)
					_A  :	Any     =					(
					    {'''feature-extraction''': ConvNextVaModel, '''image-classification''': ConvNextVaForImageClassification}
					    if is_torch_available()
					    else {}
					)

					_A  :	str     =					False
					_A  :	Dict     =					False
					_A  :	str     =					False
					_A  :	str     =					False
					_A  :	Dict     =					False



					def 					lowerCAmelCase (     self :		Optional[Any]							)	->     Dict:


												"""simple docstring"""

												__lowercase					:							List[Any]			=   ConvNextVaModelTester(self							)
												__lowercase					:							Optional[int]			=   ConfigTester(self						,   config_class=__a						,   has_text_modality=__a						,   hidden_size=37							)



					def 					lowerCAmelCase (     self :		int							)	->     Optional[int]:


												"""simple docstring"""

												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 					lowerCAmelCase (     self :		int							)	->     str:


												"""simple docstring"""

												return



					@unittest.skip(reason="""ConvNextV2 does not use inputs_embeds"""							)
					def 					lowerCAmelCase (     self :		int							)	->     Any:


												"""simple docstring"""

												pass



					@unittest.skip(reason="""ConvNextV2 does not support input and output embeddings"""							)
					def 					lowerCAmelCase (     self :		Any							)	->     Union[str, Any]:


												"""simple docstring"""

												pass



					@unittest.skip(reason="""ConvNextV2 does not use feedforward chunking"""							)
					def 					lowerCAmelCase (     self :		Any							)	->     Optional[int]:


												"""simple docstring"""

												pass



					def 					lowerCAmelCase (     self :		Union[str, Any]							)	->     List[str]:


												"""simple docstring"""

												if not self.model_tester.is_training:
																			return

												for model_class in self.all_model_classes:
																			__lowercase	,	__lowercase					:							Union[str, Any]			=   self.model_tester.prepare_config_and_inputs_with_labels()
																			__lowercase					:							str			=   True

																			if model_class.__name__ in [
																			    *get_values(__a							),
																			    *get_values(__a							),
																			]:
																										continue

																			__lowercase					:							Union[str, Any]			=   model_class(__a							)
																			model.to(__a							)
																			model.train()
																			__lowercase					:							Tuple			=   self._prepare_for_class(__a						,   __a						,   return_labels=__a							)
																			__lowercase					:							Dict			=   model(**__a							).loss
																			loss.backward()



					def 					lowerCAmelCase (     self :		Optional[int]							)	->     int:


												"""simple docstring"""

												if not self.model_tester.is_training:
																			return

												for model_class in self.all_model_classes:
																			__lowercase	,	__lowercase					:							Tuple			=   self.model_tester.prepare_config_and_inputs_with_labels()
																			__lowercase					:							Dict			=   False
																			__lowercase					:							Optional[Any]			=   True

																			if (
																			    model_class.__name__
																			    in [*get_values(__a							), *get_values(__a							)]
																			    or not model_class.supports_gradient_checkpointing
																			):
																										continue

																			__lowercase					:							List[Any]			=   model_class(__a							)
																			model.to(__a							)
																			model.gradient_checkpointing_enable()
																			model.train()
																			__lowercase					:							List[str]			=   self._prepare_for_class(__a						,   __a						,   return_labels=__a							)
																			__lowercase					:							int			=   model(**__a							).loss
																			loss.backward()



					def 					lowerCAmelCase (     self :		Tuple							)	->     Union[str, Any]:


												"""simple docstring"""

												__lowercase	,	__lowercase					:							List[str]			=   self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			__lowercase					:							int			=   model_class(__a							)
																			__lowercase					:							Optional[Any]			=   inspect.signature(model.forward							)
																			# signature.parameters is an OrderedDict => so arg_names order is deterministic
																			__lowercase					:							str			=   [*signature.parameters.keys()]

																			__lowercase					:							Optional[Any]			=   ["""pixel_values"""]
																			self.assertListEqual(arg_names[:1]						,   __a							)



					def 					lowerCAmelCase (     self :		List[str]							)	->     Union[str, Any]:


												"""simple docstring"""

												__lowercase					:							List[Any]			=   self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_model(*__a							)



					def 					lowerCAmelCase (     self :		Dict							)	->     List[str]:


												"""simple docstring"""

												def check_hidden_states_output(__a :		Any						,   __a :		Tuple						,   __a :		Tuple							):
																			__lowercase					:							Optional[Any]			=   model_class(__a							)
																			model.to(__a							)
																			model.eval()

																			with torch.no_grad():
																										__lowercase					:							int			=   model(**self._prepare_for_class(__a						,   __a							)							)

																			__lowercase					:							Optional[int]			=   outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

																			__lowercase					:							Any			=   self.model_tester.num_stages
																			self.assertEqual(len(__a							)						,   expected_num_stages + 1							)

																			# ConvNextV2's feature maps are of shape (batch_size, num_channels, height, width)
																			self.assertListEqual(
																			    list(hidden_states[0].shape[-2:]							)						,   [self.model_tester.image_size // 4, self.model_tester.image_size // 4]						,   )

												__lowercase	,	__lowercase					:							Optional[Any]			=   self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			__lowercase					:							int			=   True
																			check_hidden_states_output(__a						,   __a						,   __a							)

																			# check that output_hidden_states also work using config
																			del inputs_dict["output_hidden_states"]
																			__lowercase					:							Optional[Any]			=   True

																			check_hidden_states_output(__a						,   __a						,   __a							)



					def 					lowerCAmelCase (     self :		Dict							)	->     Union[str, Any]:


												"""simple docstring"""

												__lowercase					:							List[Any]			=   self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_image_classification(*__a							)



					@slow
					def 					lowerCAmelCase (     self :		Dict							)	->     Tuple:


												"""simple docstring"""

												for model_name in CONVNEXTV2_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			__lowercase					:							Optional[int]			=   ConvNextVaModel.from_pretrained(__a							)
																			self.assertIsNotNone(__a							)







def 					snake_case_						(   ):
							__lowercase					:							int			=   Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""					)
							return image



@require_torch
@require_vision
class 						lowerCAmelCase   (       unittest.TestCase	):

					'''simple docstring'''

					@cached_property
					def 					lowerCAmelCase (     self :		Any							)	->     List[str]:


												"""simple docstring"""

												return AutoImageProcessor.from_pretrained("""facebook/convnextv2-tiny-1k-224"""							) if is_vision_available() else None



					@slow
					def 					lowerCAmelCase (     self :		Dict							)	->     str:


												"""simple docstring"""

												__lowercase					:							Optional[Any]			=   ConvNextVaForImageClassification.from_pretrained("""facebook/convnextv2-tiny-1k-224"""							).to(__a							)

												__lowercase					:							Dict			=   self.default_image_processor
												__lowercase					:							Any			=   prepare_img()
												__lowercase					:							int			=   preprocessor(images=__a						,   return_tensors="""pt"""							).to(__a							)

												# forward pass
												with torch.no_grad():
																			__lowercase					:							int			=   model(**__a							)

												# verify the logits
												__lowercase					:							List[str]			=   torch.Size((1, 1000)							)
												self.assertEqual(outputs.logits.shape						,   __a							)

												__lowercase					:							Tuple			=   torch.tensor([0.9996, 0.1966, -0.4386]							).to(__a							)
												self.assertTrue(torch.allclose(outputs.logits[0, :3]						,   __a						,   atol=1E-4							)							)