
import inspect
import unittest

from transformers import is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device

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 MODEL_MAPPING, GLPNConfig, GLPNForDepthEstimation, GLPNModel
 from transformers.models.glpn.modeling_glpn import GLPN_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
 from PIL import Image

 from transformers import GLPNImageProcessor






class 	__magic_name__				(       lowerCAmelCase_							):






     def   UpperCAmelCase_							(							self  )->    List[str]:
         UpperCamelCase_      =	self.config_class(**self.inputs_dict  )
         self.parent.assertTrue(hasattr(lowerCamelCase_		,	"hidden_sizes"  )  )
         self.parent.assertTrue(hasattr(lowerCamelCase_		,	"num_attention_heads"  )  )
         self.parent.assertTrue(hasattr(lowerCamelCase_		,	"num_encoder_blocks"  )  )






class 	__magic_name__				:






     def __init__(							self		,	_lowercase		,	_lowercase=13		,	_lowercase=64		,	_lowercase=3		,	_lowercase=4		,	_lowercase=[2, 2, 2, 2]		,	_lowercase=[8, 4, 2, 1]		,	_lowercase=[16, 32, 64, 128]		,	_lowercase=[1, 4, 8, 16]		,	_lowercase=[1, 2, 4, 8]		,	_lowercase=True		,	_lowercase=True		,	_lowercase="gelu"		,	_lowercase=0.1		,	_lowercase=0.1		,	_lowercase=0.02		,	_lowercase=16		,	_lowercase=3		,	_lowercase=None		,	)->    Optional[Any]:
         UpperCamelCase_      =	parent
         UpperCamelCase_      =	batch_size
         UpperCamelCase_      =	image_size
         UpperCamelCase_      =	num_channels
         UpperCamelCase_      =	num_encoder_blocks
         UpperCamelCase_      =	sr_ratios
         UpperCamelCase_      =	depths
         UpperCamelCase_      =	hidden_sizes
         UpperCamelCase_      =	downsampling_rates
         UpperCamelCase_      =	num_attention_heads
         UpperCamelCase_      =	is_training
         UpperCamelCase_      =	use_labels
         UpperCamelCase_      =	hidden_act
         UpperCamelCase_      =	hidden_dropout_prob
         UpperCamelCase_      =	attention_probs_dropout_prob
         UpperCamelCase_      =	initializer_range
         UpperCamelCase_      =	decoder_hidden_size
         UpperCamelCase_      =	num_labels
         UpperCamelCase_      =	scope






     def   UpperCAmelCase_							(							self  )->    List[str]:
         UpperCamelCase_      =	floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]  )

         UpperCamelCase_      =	None
         if self.use_labels:
             UpperCamelCase_      =	ids_tensor([self.batch_size, self.image_size, self.image_size]		,	self.num_labels  )

         UpperCamelCase_      =	self.get_config()
         return config, pixel_values, labels






     def   UpperCAmelCase_							(							self  )->    Optional[Any]:
         return GLPNConfig(
             image_size=self.image_size		,	num_channels=self.num_channels		,	num_encoder_blocks=self.num_encoder_blocks		,	depths=self.depths		,	hidden_sizes=self.hidden_sizes		,	num_attention_heads=self.num_attention_heads		,	hidden_act=self.hidden_act		,	hidden_dropout_prob=self.hidden_dropout_prob		,	attention_probs_dropout_prob=self.attention_probs_dropout_prob		,	initializer_range=self.initializer_range		,	decoder_hidden_size=self.decoder_hidden_size		,	)






     def   UpperCAmelCase_							(							self		,	_lowercase		,	_lowercase		,	_lowercase  )->    Optional[int]:
         UpperCamelCase_      =	GLPNModel(config=lowerCamelCase_  )
         model.to(lowerCamelCase_  )
         model.eval()
         UpperCamelCase_      =	model(lowerCamelCase_  )
         UpperCamelCase_      =	UpperCamelCase_      =	self.image_size // (self.downsampling_rates[-1] * 2)
         self.parent.assertEqual(
             result.last_hidden_state.shape		,	(self.batch_size, self.hidden_sizes[-1], expected_height, expected_width)  )






     def   UpperCAmelCase_							(							self		,	_lowercase		,	_lowercase		,	_lowercase  )->    Any:
         UpperCamelCase_      =	self.num_labels
         UpperCamelCase_      =	GLPNForDepthEstimation(lowerCamelCase_  )
         model.to(lowerCamelCase_  )
         model.eval()
         UpperCamelCase_      =	model(lowerCamelCase_  )
         self.parent.assertEqual(result.predicted_depth.shape		,	(self.batch_size, self.image_size, self.image_size)  )
         UpperCamelCase_      =	model(lowerCamelCase_		,	labels=lowerCamelCase_  )
         self.parent.assertEqual(result.predicted_depth.shape		,	(self.batch_size, self.image_size, self.image_size)  )






     def   UpperCAmelCase_							(							self  )->    Any:
         UpperCamelCase_      =	self.prepare_config_and_inputs()
         UpperCamelCase_     ,					UpperCamelCase_     ,					UpperCamelCase_      =	config_and_inputs
         UpperCamelCase_      =	{"pixel_values": pixel_values}
         return config, inputs_dict






@require_torch
class 	__magic_name__				(       lowerCAmelCase_ ,			lowerCAmelCase_ ,			unittest.TestCase							):
     UpperCamelCase_  :Any								=			(GLPNModel, GLPNForDepthEstimation) if is_torch_available() else ()
     UpperCamelCase_  :int								=			(
         {'depth-estimation': GLPNForDepthEstimation, 'feature-extraction': GLPNModel} if is_torch_available() else {}
     )

     UpperCamelCase_  :List[Any]								=			False
     UpperCamelCase_  :Any								=			False
     UpperCamelCase_  :List[str]								=			False






     def   UpperCAmelCase_							(							self  )->    List[Any]:
         UpperCamelCase_      =	GLPNModelTester(self  )
         UpperCamelCase_      =	GLPNConfigTester(self		,	config_class=lowerCamelCase_  )






     def   UpperCAmelCase_							(							self  )->    Dict:
         self.config_tester.run_common_tests()






     def   UpperCAmelCase_							(							self  )->    Optional[Any]:
         UpperCamelCase_      =	self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_model(*lowerCamelCase_  )






     def   UpperCAmelCase_							(							self  )->    List[Any]:
         UpperCamelCase_      =	self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_depth_estimation(*lowerCamelCase_  )






     @unittest.skip("GLPN does not use inputs_embeds"  )
     def   UpperCAmelCase_							(							self  )->    List[Any]:
         pass






     @unittest.skip("GLPN does not have get_input_embeddings method and get_output_embeddings methods"  )
     def   UpperCAmelCase_							(							self  )->    Union[str, Any]:
         pass






     def   UpperCAmelCase_							(							self  )->    int:
         UpperCamelCase_     ,					UpperCamelCase_      =	self.model_tester.prepare_config_and_inputs_for_common()

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

             UpperCamelCase_      =	["pixel_values"]
             self.assertListEqual(arg_names[:1]		,	lowerCamelCase_  )






     def   UpperCAmelCase_							(							self  )->    Tuple:
         UpperCamelCase_     ,					UpperCamelCase_      =	self.model_tester.prepare_config_and_inputs_for_common()
         UpperCamelCase_      =	True

         for model_class in self.all_model_classes:
             UpperCamelCase_      =	True
             UpperCamelCase_      =	False
             UpperCamelCase_      =	True
             UpperCamelCase_      =	model_class(lowerCamelCase_  )
             model.to(lowerCamelCase_  )
             model.eval()
             with torch.no_grad():
                 UpperCamelCase_      =	model(**self._prepare_for_class(lowerCamelCase_		,	lowerCamelCase_  )  )
             UpperCamelCase_      =	outputs.attentions

             UpperCamelCase_      =	sum(self.model_tester.depths  )
             self.assertEqual(len(lowerCamelCase_  )		,	lowerCamelCase_  )

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

             self.assertEqual(len(lowerCamelCase_  )		,	lowerCamelCase_  )

             # verify the first attentions (first block, first layer)
             UpperCamelCase_      =	(self.model_tester.image_size // 4) ** 2
             UpperCamelCase_      =	(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
             self.assertListEqual(
                 list(attentions[0].shape[-3:]  )		,	[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]		,	)

             # verify the last attentions (last block, last layer)
             UpperCamelCase_      =	(self.model_tester.image_size // 32) ** 2
             UpperCamelCase_      =	(self.model_tester.image_size // (32 * self.model_tester.sr_ratios[-1])) ** 2
             self.assertListEqual(
                 list(attentions[-1].shape[-3:]  )		,	[self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len]		,	)
             UpperCamelCase_      =	len(lowerCamelCase_  )

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

             self.assertEqual(out_len + 1		,	len(lowerCamelCase_  )  )

             UpperCamelCase_      =	outputs.attentions

             self.assertEqual(len(lowerCamelCase_  )		,	lowerCamelCase_  )
             # verify the first attentions (first block, first layer)
             UpperCamelCase_      =	(self.model_tester.image_size // 4) ** 2
             UpperCamelCase_      =	(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
             self.assertListEqual(
                 list(self_attentions[0].shape[-3:]  )		,	[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]		,	)






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

         def check_hidden_states_output(_lowercase		,	_lowercase		,	_lowercase  ):
             UpperCamelCase_      =	model_class(lowerCamelCase_  )
             model.to(lowerCamelCase_  )
             model.eval()

             with torch.no_grad():
                 UpperCamelCase_      =	model(**self._prepare_for_class(lowerCamelCase_		,	lowerCamelCase_  )  )

             UpperCamelCase_      =	outputs.hidden_states

             UpperCamelCase_      =	self.model_tester.num_encoder_blocks
             self.assertEqual(len(lowerCamelCase_  )		,	lowerCamelCase_  )

             # verify the first hidden states (first block)
             self.assertListEqual(
                 list(hidden_states[0].shape[-3:]  )		,	[
                     self.model_tester.hidden_sizes[0],
                     self.model_tester.image_size // 4,
                     self.model_tester.image_size // 4,
                 ]		,	)

         UpperCamelCase_     ,					UpperCamelCase_      =	self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             UpperCamelCase_      =	True
             check_hidden_states_output(lowerCamelCase_		,	lowerCamelCase_		,	lowerCamelCase_  )

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

             check_hidden_states_output(lowerCamelCase_		,	lowerCamelCase_		,	lowerCamelCase_  )






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

         if not self.model_tester.is_training:
             return

         UpperCamelCase_     ,					UpperCamelCase_      =	self.model_tester.prepare_config_and_inputs_for_common()
         UpperCamelCase_      =	True

         for model_class in self.all_model_classes:
             if model_class in get_values(lowerCamelCase_  ):
                 continue
             # TODO: remove the following 3 lines once we have a MODEL_FOR_DEPTH_ESTIMATION_MAPPING
             # this can then be incorporated into _prepare_for_class in test_modeling_common.py
             if model_class.__name__ == "GLPNForDepthEstimation":
                 UpperCamelCase_     ,					UpperCamelCase_     ,					UpperCamelCase_     ,					UpperCamelCase_      =	inputs_dict["pixel_values"].shape
                 UpperCamelCase_      =	torch.zeros(
                     [self.model_tester.batch_size, height, width]		,	device=lowerCamelCase_  ).long()
             UpperCamelCase_      =	model_class(lowerCamelCase_  )
             model.to(lowerCamelCase_  )
             model.train()
             UpperCamelCase_      =	self._prepare_for_class(lowerCamelCase_		,	lowerCamelCase_		,	return_labels=lowerCamelCase_  )
             UpperCamelCase_      =	model(**lowerCamelCase_  ).loss
             loss.backward()






     @slow
     def   UpperCAmelCase_							(							self  )->    int:

         for model_name in GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
             UpperCamelCase_      =	GLPNModel.from_pretrained(lowerCamelCase_  )
             self.assertIsNotNone(lowerCamelCase_  )




def  lowerCAmelCase(			)->	int:



    """simple docstring"""






    UpperCamelCase_      =	Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png" )
    return image






@require_torch
@require_vision
@slow
class 	__magic_name__				(       unittest.TestCase							):






     @slow
     def   UpperCAmelCase_							(							self  )->    Optional[Any]:
         UpperCamelCase_      =	GLPNImageProcessor.from_pretrained(GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[0]  )
         UpperCamelCase_      =	GLPNForDepthEstimation.from_pretrained(GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[0]  ).to(lowerCamelCase_  )

         UpperCamelCase_      =	prepare_img()
         UpperCamelCase_      =	image_processor(images=lowerCamelCase_		,	return_tensors="pt"  ).to(lowerCamelCase_  )

         # forward pass
         with torch.no_grad():
             UpperCamelCase_      =	model(**lowerCamelCase_  )

         # verify the predicted depth
         UpperCamelCase_      =	torch.Size([1, 480, 640]  )
         self.assertEqual(outputs.predicted_depth.shape		,	lowerCamelCase_  )

         UpperCamelCase_      =	torch.tensor(
             [[3.4_291, 2.7_865, 2.5_151], [3.2_841, 2.7_021, 2.3_502], [3.1_147, 2.4_625, 2.2_481]]  ).to(lowerCamelCase_  )

         self.assertTrue(torch.allclose(outputs.predicted_depth[0, :3, :3]		,	lowerCamelCase_		,	atol=1e-4  )  )



from __future__ import annotations




def  lowerCAmelCase(			SCREAMING_SNAKE_CASE_ )->	str:



    """simple docstring"""






    global graph, reversed_graph, scc, component, visit, stack
    if visit[u]:
        return
    UpperCamelCase_      =	True
    for v in graph[u]:
        dfs(SCREAMING_SNAKE_CASE_ )
    stack.append(SCREAMING_SNAKE_CASE_ )




def  lowerCAmelCase(			SCREAMING_SNAKE_CASE_ )->	Dict:



    """simple docstring"""






    global graph, reversed_graph, scc, component, visit, stack
    if visit[u]:
        return
    UpperCamelCase_      =	True
    component.append(SCREAMING_SNAKE_CASE_ )
    for v in reversed_graph[u]:
        dfsa(SCREAMING_SNAKE_CASE_ )




def  lowerCAmelCase(			)->	Dict:



    """simple docstring"""






    global graph, reversed_graph, scc, component, visit, stack
    for i in range(SCREAMING_SNAKE_CASE_ ):
        dfs(SCREAMING_SNAKE_CASE_ )
    UpperCamelCase_      =	[False] * n
    for i in stack[::-1]:
        if visit[i]:
            continue
        UpperCamelCase_      =	[]
        dfsa(SCREAMING_SNAKE_CASE_ )
        scc.append(SCREAMING_SNAKE_CASE_ )
    return scc


if __name__ == "__main__":
 # n - no of nodes, m - no of edges
 SCREAMING_SNAKE_CASE  ,       SCREAMING_SNAKE_CASE		:str				  =    list(map(int, input().strip().split()))

 SCREAMING_SNAKE_CASE		:list[list[int]]				  =    [[] for _ in range(n)]  # graph
 SCREAMING_SNAKE_CASE		:list[list[int]]				  =    [[] for i in range(n)]  # reversed graph
 # input graph data (edges)
 for _ in range(m):
  SCREAMING_SNAKE_CASE  ,       SCREAMING_SNAKE_CASE		:str				  =    list(map(int, input().strip().split()))
  graph[u].append(v)
  reversed_graph[v].append(u)

 SCREAMING_SNAKE_CASE		:list[int]				  =    []
 SCREAMING_SNAKE_CASE		:list[bool]				  =    [False] * n
 SCREAMING_SNAKE_CASE		:list[int]				  =    []
 SCREAMING_SNAKE_CASE		:list[int]				  =    []
 print(kosaraju())
