




'''simple docstring'''
import unittest

from transformers import FunnelConfig, FunnelTokenizer, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device

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


if is_torch_available():
							import torch

							from transformers import (
							    MODEL_FOR_PRETRAINING_MAPPING,
							    FunnelBaseModel,
							    FunnelForMaskedLM,
							    FunnelForMultipleChoice,
							    FunnelForPreTraining,
							    FunnelForQuestionAnswering,
							    FunnelForSequenceClassification,
							    FunnelForTokenClassification,
							    FunnelModel,
							)
class 					__UpperCAmelCase							:



					'''simple docstring'''





					def __init__(  self    :	str			,					_lowercase    :	Optional[int]			,					_lowercase    :	Any=13			,					_lowercase    :	Tuple=7			,					_lowercase    :	Optional[Any]=True			,					_lowercase    :	Union[str, Any]=True			,					_lowercase    :	str=True			,					_lowercase    :	Union[str, Any]=True			,					_lowercase    :	Union[str, Any]=99			,					_lowercase    :	int=[1, 1, 2]			,					_lowercase    :	str=1			,					_lowercase    :	List[Any]=32			,					_lowercase    :	Union[str, Any]=4			,					_lowercase    :	int=8			,					_lowercase    :	int=37			,					_lowercase    :	Tuple="gelu_new"			,					_lowercase    :	Union[str, Any]=0.1			,					_lowercase    :	List[str]=0.1			,					_lowercase    :	int=0.0			,					_lowercase    :	Any=512			,					_lowercase    :	Tuple=3			,					_lowercase    :	Optional[Any]=0.02			,					_lowercase    :	Optional[Any]=3			,					_lowercase    :	Any=4			,					_lowercase    :	Optional[Any]=None			,					_lowercase    :	Dict=False			,					)						->       List[Any]:
								A_       		=   parent
								A_       		=   batch_size
								A_       		=   seq_length
								A_       		=   is_training
								A_       		=   use_input_mask
								A_       		=   use_token_type_ids
								A_       		=   use_labels
								A_       		=   vocab_size
								A_       		=   block_sizes
								A_       		=   num_decoder_layers
								A_       		=   d_model
								A_       		=   n_head
								A_       		=   d_head
								A_       		=   d_inner
								A_       		=   hidden_act
								A_       		=   hidden_dropout
								A_       		=   attention_dropout
								A_       		=   activation_dropout
								A_       		=   max_position_embeddings
								A_       		=   type_vocab_size
								A_       		=   2
								A_       		=   num_labels
								A_       		=   num_choices
								A_       		=   scope
								A_       		=   initializer_std

								# Used in the tests to check the size of the first attention layer
								A_       		=   n_head
								# Used in the tests to check the size of the first hidden state
								A_       		=   self.d_model
								# Used in the tests to check the number of output hidden states/attentions
								A_       		=   sum(self.block_sizes) + (0 if base else self.num_decoder_layers)
								# FunnelModel adds two hidden layers: input embeddings and the sum of the upsampled encoder hidden state with
								# the last hidden state of the first block (which is the first hidden state of the decoder).
								if not base:
											A_       		=   self.num_hidden_layers + 2



					def 						__snake_case	(  self    :	Optional[Any])						->       Union[str, Any]:
								A_       		=   ids_tensor([self.batch_size, self.seq_length]			,					self.vocab_size)

								A_       		=   None
								if self.use_input_mask:
											A_       		=   ids_tensor([self.batch_size, self.seq_length]			,					vocab_size=2)

								A_       		=   None
								if self.use_token_type_ids:
											A_       		=   ids_tensor([self.batch_size, self.seq_length]			,					self.type_vocab_size)

								A_       		=   None
								A_       		=   None
								A_       		=   None
								if self.use_labels:
											A_       		=   ids_tensor([self.batch_size]			,					self.type_sequence_label_size)
											A_       		=   ids_tensor([self.batch_size, self.seq_length]			,					self.num_labels)
											A_       		=   ids_tensor([self.batch_size]			,					self.num_choices)
											A_       		=   ids_tensor([self.batch_size, self.seq_length]			,					1)

								A_       		=   self.get_config()

								return (
								    config,
								    input_ids,
								    token_type_ids,
								    input_mask,
								    sequence_labels,
								    token_labels,
								    choice_labels,
								    fake_token_labels,
								)



					def 						__snake_case	(  self    :	List[Any])						->       Optional[int]:
								return FunnelConfig(
								    vocab_size=self.vocab_size			,					block_sizes=self.block_sizes			,					num_decoder_layers=self.num_decoder_layers			,					d_model=self.d_model			,					n_head=self.n_head			,					d_head=self.d_head			,					d_inner=self.d_inner			,					hidden_act=self.hidden_act			,					hidden_dropout=self.hidden_dropout			,					attention_dropout=self.attention_dropout			,					activation_dropout=self.activation_dropout			,					max_position_embeddings=self.max_position_embeddings			,					type_vocab_size=self.type_vocab_size			,					initializer_std=self.initializer_std			,					)



					def 						__snake_case	(  self    :	Optional[int]			,					_lowercase    :	List[str]			,					_lowercase    :	Tuple			,					_lowercase    :	Optional[int]			,					_lowercase    :	int			,					_lowercase    :	List[str]			,					_lowercase    :	Union[str, Any]			,					_lowercase    :	int			,					_lowercase    :	Optional[Any]			,					)						->       Dict:
								A_       		=   FunnelModel(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase)
								A_       		=   model(_lowercase			,					token_type_ids=_lowercase)
								A_       		=   model(_lowercase)
								self.parent.assertEqual(result.last_hidden_state.shape			,					(self.batch_size, self.seq_length, self.d_model))

								A_       		=   False
								A_       		=   model(_lowercase)
								self.parent.assertEqual(result.last_hidden_state.shape			,					(self.batch_size, self.seq_length, self.d_model))

								A_       		=   False
								A_       		=   model(_lowercase)
								self.parent.assertEqual(result.last_hidden_state.shape			,					(self.batch_size, self.seq_length, self.d_model))



					def 						__snake_case	(  self    :	List[str]			,					_lowercase    :	Any			,					_lowercase    :	int			,					_lowercase    :	Optional[Any]			,					_lowercase    :	str			,					_lowercase    :	List[str]			,					_lowercase    :	Optional[Any]			,					_lowercase    :	Tuple			,					_lowercase    :	Tuple			,					)						->       Any:
								A_       		=   FunnelBaseModel(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase)
								A_       		=   model(_lowercase			,					token_type_ids=_lowercase)
								A_       		=   model(_lowercase)
								self.parent.assertEqual(result.last_hidden_state.shape			,					(self.batch_size, 2, self.d_model))

								A_       		=   False
								A_       		=   model(_lowercase)
								self.parent.assertEqual(result.last_hidden_state.shape			,					(self.batch_size, 3, self.d_model))

								A_       		=   False
								A_       		=   model(_lowercase)
								self.parent.assertEqual(result.last_hidden_state.shape			,					(self.batch_size, 2, self.d_model))



					def 						__snake_case	(  self    :	Optional[int]			,					_lowercase    :	Optional[Any]			,					_lowercase    :	Optional[Any]			,					_lowercase    :	Tuple			,					_lowercase    :	str			,					_lowercase    :	Union[str, Any]			,					_lowercase    :	List[str]			,					_lowercase    :	Optional[Any]			,					_lowercase    :	str			,					)						->       List[str]:
								A_       		=   self.num_labels
								A_       		=   FunnelForPreTraining(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase			,					labels=_lowercase)
								self.parent.assertEqual(result.logits.shape			,					(self.batch_size, self.seq_length))



					def 						__snake_case	(  self    :	str			,					_lowercase    :	Any			,					_lowercase    :	int			,					_lowercase    :	str			,					_lowercase    :	Tuple			,					_lowercase    :	str			,					_lowercase    :	str			,					_lowercase    :	int			,					_lowercase    :	int			,					)						->       Any:
								A_       		=   FunnelForMaskedLM(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase			,					labels=_lowercase)
								self.parent.assertEqual(result.logits.shape			,					(self.batch_size, self.seq_length, self.vocab_size))



					def 						__snake_case	(  self    :	str			,					_lowercase    :	Optional[int]			,					_lowercase    :	List[Any]			,					_lowercase    :	Optional[Any]			,					_lowercase    :	List[Any]			,					_lowercase    :	Union[str, Any]			,					_lowercase    :	Any			,					_lowercase    :	str			,					_lowercase    :	Union[str, Any]			,					)						->       List[Any]:
								A_       		=   self.num_labels
								A_       		=   FunnelForSequenceClassification(_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase			,					labels=_lowercase)
								self.parent.assertEqual(result.logits.shape			,					(self.batch_size, self.num_labels))



					def 						__snake_case	(  self    :	List[Any]			,					_lowercase    :	str			,					_lowercase    :	Union[str, Any]			,					_lowercase    :	int			,					_lowercase    :	Any			,					_lowercase    :	Optional[Any]			,					_lowercase    :	Optional[int]			,					_lowercase    :	Any			,					_lowercase    :	Dict			,					)						->       Dict:
								A_       		=   self.num_choices
								A_       		=   FunnelForMultipleChoice(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   input_ids.unsqueeze(1).expand(-1			,					self.num_choices			,					-1).contiguous()
								A_       		=   token_type_ids.unsqueeze(1).expand(-1			,					self.num_choices			,					-1).contiguous()
								A_       		=   input_mask.unsqueeze(1).expand(-1			,					self.num_choices			,					-1).contiguous()
								A_       		=   model(
								    _lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase			,					labels=_lowercase			,					)
								self.parent.assertEqual(result.logits.shape			,					(self.batch_size, self.num_choices))



					def 						__snake_case	(  self    :	List[str]			,					_lowercase    :	Dict			,					_lowercase    :	Optional[int]			,					_lowercase    :	Optional[int]			,					_lowercase    :	int			,					_lowercase    :	Optional[Any]			,					_lowercase    :	Optional[int]			,					_lowercase    :	Tuple			,					_lowercase    :	Optional[Any]			,					)						->       str:
								A_       		=   self.num_labels
								A_       		=   FunnelForTokenClassification(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase			,					labels=_lowercase)
								self.parent.assertEqual(result.logits.shape			,					(self.batch_size, self.seq_length, self.num_labels))



					def 						__snake_case	(  self    :	Union[str, Any]			,					_lowercase    :	Optional[Any]			,					_lowercase    :	Any			,					_lowercase    :	Union[str, Any]			,					_lowercase    :	Any			,					_lowercase    :	List[Any]			,					_lowercase    :	str			,					_lowercase    :	str			,					_lowercase    :	List[str]			,					)						->       str:
								A_       		=   FunnelForQuestionAnswering(config=_lowercase)
								model.to(_lowercase)
								model.eval()
								A_       		=   model(
								    _lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase			,					start_positions=_lowercase			,					end_positions=_lowercase			,					)
								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 						__snake_case	(  self    :	Union[str, Any])						->       Any:
								A_       		=   self.prepare_config_and_inputs()
								(
								    A_   
								)       		=   config_and_inputs
								A_       		=   {"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
								return config, inputs_dict





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



					'''simple docstring'''





					_UpperCamelCase  	=		False
					_UpperCamelCase  	=		False
					_UpperCamelCase  	=		(
					    (
					        FunnelModel,
					        FunnelForMaskedLM,
					        FunnelForPreTraining,
					        FunnelForQuestionAnswering,
					        FunnelForTokenClassification,
					    )
					    if is_torch_available()
					    else ()
					)
					_UpperCamelCase  	=		(
					    {
					        "feature-extraction": (FunnelBaseModel, FunnelModel),
					        "fill-mask": FunnelForMaskedLM,
					        "question-answering": FunnelForQuestionAnswering,
					        "text-classification": FunnelForSequenceClassification,
					        "token-classification": FunnelForTokenClassification,
					        "zero-shot": FunnelForSequenceClassification,
					    }
					    if is_torch_available()
					    else {}
					)



					def 						__snake_case	(  self    :	List[str]			,					_lowercase    :	List[Any]			,					_lowercase    :	List[str]			,					_lowercase    :	List[str]=False)						->       Union[str, Any]:
								A_       		=   super()._prepare_for_class(_lowercase			,					_lowercase			,					return_labels=_lowercase)

								if return_labels:
											if model_class in get_values(_lowercase):
														A_       		=   torch.zeros(
														    (self.model_tester.batch_size, self.model_tester.seq_length)			,					dtype=torch.long			,					device=_lowercase)
								return inputs_dict



					def 						__snake_case	(  self    :	Any)						->       Any:
								A_       		=   FunnelModelTester(self)
								A_       		=   ConfigTester(self			,					config_class=_lowercase)



					def 						__snake_case	(  self    :	List[Any])						->       int:
								self.config_tester.run_common_tests()



					def 						__snake_case	(  self    :	Any)						->       Dict:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_model(*_lowercase)



					def 						__snake_case	(  self    :	Optional[Any])						->       Optional[int]:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_pretraining(*_lowercase)



					def 						__snake_case	(  self    :	int)						->       List[str]:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_masked_lm(*_lowercase)



					def 						__snake_case	(  self    :	Optional[Any])						->       Dict:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_token_classification(*_lowercase)



					def 						__snake_case	(  self    :	int)						->       str:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_question_answering(*_lowercase)



					def 						__snake_case	(  self    :	Any			,					_lowercase    :	Optional[Any])						->       Any:






								if hasattr(_lowercase			,					'weight') and module.weight is not None:
											module.weight.data.fill_(3)
								if hasattr(_lowercase			,					'bias') and module.bias is not None:
											module.bias.data.fill_(3)

								for param in ["r_w_bias", "r_r_bias", "r_kernel", "r_s_bias", "seg_embed"]:
											if hasattr(_lowercase			,					_lowercase) and getattr(_lowercase			,					_lowercase) is not None:
														A_       		=   getattr(_lowercase			,					_lowercase)
														weight.data.fill_(3)





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



					'''simple docstring'''





					_UpperCamelCase  	=		False
					_UpperCamelCase  	=		False
					_UpperCamelCase  	=		(
					    (FunnelBaseModel, FunnelForMultipleChoice, FunnelForSequenceClassification) if is_torch_available() else ()
					)



					def 						__snake_case	(  self    :	Any)						->       List[Any]:
								A_       		=   FunnelModelTester(self			,					base=_lowercase)
								A_       		=   ConfigTester(self			,					config_class=_lowercase)



					def 						__snake_case	(  self    :	int)						->       Tuple:
								self.config_tester.run_common_tests()



					def 						__snake_case	(  self    :	Dict)						->       Any:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_base_model(*_lowercase)



					def 						__snake_case	(  self    :	Optional[Any])						->       List[Any]:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_sequence_classification(*_lowercase)



					def 						__snake_case	(  self    :	str)						->       Dict:
								A_       		=   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_multiple_choice(*_lowercase)



					def 						__snake_case	(  self    :	Tuple)						->       Tuple:
								A_       		=   self.model_tester.prepare_config_and_inputs_for_common()
								A_       		=   True

								for model_class in self.all_model_classes:
											if model_class.__name__ == "FunnelBaseModel":
														continue
											A_       		=   model_class(_lowercase)
											model.to(_lowercase)
											model.train()
											A_       		=   self._prepare_for_class(_lowercase			,					_lowercase			,					return_labels=_lowercase)
											A_       		=   model(**_lowercase).loss
											loss.backward()



					def 						__snake_case	(  self    :	Tuple			,					_lowercase    :	List[str])						->       Tuple:






								if hasattr(_lowercase			,					'weight') and module.weight is not None:
											module.weight.data.fill_(3)
								if hasattr(_lowercase			,					'bias') and module.bias is not None:
											module.bias.data.fill_(3)

								for param in ["r_w_bias", "r_r_bias", "r_kernel", "r_s_bias", "seg_embed"]:
											if hasattr(_lowercase			,					_lowercase) and getattr(_lowercase			,					_lowercase) is not None:
														A_       		=   getattr(_lowercase			,					_lowercase)
														weight.data.fill_(3)





@require_torch
@require_sentencepiece
@require_tokenizers
class 					__UpperCAmelCase							(    unittest.TestCase							):



					'''simple docstring'''





					def 						__snake_case	(  self    :	Optional[Any])						->       int:
								A_       		=   13
								A_       		=   7
								A_       		=   torch.arange(0			,					batch_size * sequence_length).long().reshape(_lowercase			,					_lowercase)
								A_       		=   [0, 1, 2, 3, 4, 5, 6, 4, 1, 3, 5, 0, 1]
								A_       		=   torch.tensor([[2] + [0] * a + [1] * (sequence_length - a - 1) for a in lengths])

								A_       		=   FunnelModel.from_pretrained('sgugger/funnel-random-tiny')
								A_       		=   model(_lowercase			,					token_type_ids=_lowercase)[0].abs()

								A_       		=   torch.tensor(2_344.8_352)
								A_       		=   torch.tensor(0.80_52)
								self.assertTrue(torch.allclose(output.sum()			,					_lowercase			,					atol=1E-4))
								self.assertTrue(torch.allclose(output.mean()			,					_lowercase			,					atol=1E-4))

								A_       		=   torch.tensor([[1] * 7, [1] * 4 + [0] * 3] * 6 + [[0, 1, 1, 0, 0, 1, 1]])
								A_       		=   model(_lowercase			,					attention_mask=_lowercase			,					token_type_ids=_lowercase)[0].abs()

								A_       		=   torch.tensor(2_343.8_425)
								A_       		=   torch.tensor(0.80_49)
								self.assertTrue(torch.allclose(output.sum()			,					_lowercase			,					atol=1E-4))
								self.assertTrue(torch.allclose(output.mean()			,					_lowercase			,					atol=1E-4))



					@slow
					def 						__snake_case	(  self    :	int)						->       str:
								A_       		=   FunnelTokenizer.from_pretrained('huggingface/funnel-small')
								A_       		=   FunnelModel.from_pretrained('huggingface/funnel-small')
								A_       		=   tokenizer('Hello! I am the Funnel Transformer model.'			,					return_tensors='pt')
								A_       		=   model(**_lowercase)[0]

								A_       		=   torch.tensor(2_35.72_46)
								A_       		=   torch.tensor(0.02_56)
								self.assertTrue(torch.allclose(output.sum()			,					_lowercase			,					atol=1E-4))
								self.assertTrue(torch.allclose(output.mean()			,					_lowercase			,					atol=1E-4))










'''simple docstring'''
from __future__ import annotations





def  lowerCamelCase(       SCREAMING_SNAKE_CASE_    )		->		Optional[int]:
			global graph, reversed_graph, scc, component, visit, stack
			if visit[u]:
						return
			A_       		=   True
			for v in graph[u]:
						dfs(SCREAMING_SNAKE_CASE_    )
			stack.append(SCREAMING_SNAKE_CASE_    )





def  lowerCamelCase(       SCREAMING_SNAKE_CASE_    )		->		List[Any]:
			global graph, reversed_graph, scc, component, visit, stack
			if visit[u]:
						return
			A_       		=   True
			component.append(SCREAMING_SNAKE_CASE_    )
			for v in reversed_graph[u]:
						dfsa(SCREAMING_SNAKE_CASE_    )





def  lowerCamelCase(       )		->		int:
			global graph, reversed_graph, scc, component, visit, stack
			for i in range(SCREAMING_SNAKE_CASE_    ):
						dfs(SCREAMING_SNAKE_CASE_    )
			A_       		=   [False] * n
			for i in stack[::-1]:
						if visit[i]:
									continue
						A_       		=   []
						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 =	list(map(int, input().strip().split()))

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

							_SCREAMING_SNAKE_CASE =	[]
							_SCREAMING_SNAKE_CASE =	[False] * n
							_SCREAMING_SNAKE_CASE =	[]
							_SCREAMING_SNAKE_CASE =	[]
							print(kosaraju())




