'''simple docstring'''




from __future__ import annotations

import unittest
import warnings

from transformers import AutoTokenizer, MarianConfig, MarianTokenizer, TranslationPipeline, is_tf_available
from transformers.testing_utils import require_sentencepiece, require_tf, require_tokenizers, slow
from transformers.utils import cached_property

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
						import tensorflow as tf

						from transformers import TFAutoModelForSeqaSeqLM, TFMarianModel, TFMarianMTModel





@require_tf
class        __magic_name__		:
			UpperCamelCase__							=			MarianConfig
			UpperCamelCase__							=			{}
			UpperCamelCase__							=			'''gelu'''







			def __init__(      self							:    Optional[Any]							,     lowercase_							:    Tuple							,     lowercase_							:    Optional[int]=13							,     lowercase_							:    Dict=7							,     lowercase_							:    str=True							,     lowercase_							:    str=False							,     lowercase_							:    Tuple=99							,     lowercase_							:    int=32							,     lowercase_							:    int=2							,     lowercase_							:    Optional[int]=4							,     lowercase_							:    Optional[int]=37							,     lowercase_							:    Any=0.1							,     lowercase_							:    List[Any]=0.1							,     lowercase_							:    Union[str, Any]=20							,     lowercase_							:    List[str]=2							,     lowercase_							:    int=1							,     lowercase_							:    Union[str, Any]=0							,     ):
										lowercase_   :     str									=			parent
										lowercase_   :     Any									=			batch_size
										lowercase_   :     List[Any]									=			seq_length
										lowercase_   :     str									=			is_training
										lowercase_   :     str									=			use_labels
										lowercase_   :     str									=			vocab_size
										lowercase_   :     Optional[Any]									=			hidden_size
										lowercase_   :     Optional[Any]									=			num_hidden_layers
										lowercase_   :     List[Any]									=			num_attention_heads
										lowercase_   :     List[Any]									=			intermediate_size

										lowercase_   :     List[str]									=			hidden_dropout_prob
										lowercase_   :     Union[str, Any]									=			attention_probs_dropout_prob
										lowercase_   :     str									=			max_position_embeddings
										lowercase_   :     Optional[int]									=			eos_token_id
										lowercase_   :     Dict									=			pad_token_id
										lowercase_   :     Any									=			bos_token_id







			def       SCREAMING_SNAKE_CASE_	(      self							:    Optional[int]       ):
										lowercase_   :     Optional[int]									=			ids_tensor([self.batch_size, self.seq_length - 1]							,     self.vocab_size       )
										lowercase_   :     Tuple									=			tf.expand_dims(tf.constant([self.eos_token_id] * self.batch_size       )							,     1       )
										lowercase_   :     Dict									=			tf.concat([input_ids, eos_tensor]							,     axis=1       )

										lowercase_   :     List[Any]									=			ids_tensor([self.batch_size, self.seq_length]							,     self.vocab_size       )

										lowercase_   :     List[Any]									=			self.config_cls(
										    vocab_size=self.vocab_size							,     d_model=self.hidden_size							,     encoder_layers=self.num_hidden_layers							,     decoder_layers=self.num_hidden_layers							,     encoder_attention_heads=self.num_attention_heads							,     decoder_attention_heads=self.num_attention_heads							,     encoder_ffn_dim=self.intermediate_size							,     decoder_ffn_dim=self.intermediate_size							,     dropout=self.hidden_dropout_prob							,     attention_dropout=self.attention_probs_dropout_prob							,     max_position_embeddings=self.max_position_embeddings							,     eos_token_ids=[2]							,     bos_token_id=self.bos_token_id							,     pad_token_id=self.pad_token_id							,     decoder_start_token_id=self.pad_token_id							,     **self.config_updates							,     )
										lowercase_   :     List[Any]									=			prepare_marian_inputs_dict(lowercase_							,     lowercase_							,     lowercase_       )
										return config, inputs_dict







			def       SCREAMING_SNAKE_CASE_	(      self							:    Optional[Any]							,     lowercase_							:    List[Any]							,     lowercase_							:    Optional[int]       ):
										lowercase_   :     Any									=			TFMarianModel(config=lowercase_       ).get_decoder()
										lowercase_   :     Optional[Any]									=			inputs_dict["""input_ids"""]

										lowercase_   :     Tuple									=			input_ids[:1, :]
										lowercase_   :     Optional[Any]									=			inputs_dict["""attention_mask"""][:1, :]
										lowercase_   :     List[str]									=			inputs_dict["""head_mask"""]
										lowercase_   :     Dict									=			1

										# first forward pass
										lowercase_   :     List[Any]									=			model(lowercase_							,     attention_mask=lowercase_							,     head_mask=lowercase_							,     use_cache=lowercase_       )

										lowercase_		,		lowercase_   :     Any									=			outputs.to_tuple()

										# create hypothetical next token and extent to next_input_ids
										lowercase_   :     Any									=			ids_tensor((self.batch_size, 3)							,     config.vocab_size       )
										lowercase_   :     Dict									=			tf.cast(ids_tensor((self.batch_size, 3)							,     2       )							,     tf.inta       )

										# append to next input_ids and
										lowercase_   :     Dict									=			tf.concat([input_ids, next_tokens]							,     axis=-1       )
										lowercase_   :     Dict									=			tf.concat([attention_mask, next_attn_mask]							,     axis=-1       )

										lowercase_   :     Optional[int]									=			model(lowercase_							,     attention_mask=lowercase_       )[0]
										lowercase_   :     Union[str, Any]									=			model(lowercase_							,     attention_mask=lowercase_							,     past_key_values=lowercase_       )[0]

										self.parent.assertEqual(next_tokens.shape[1]							,     output_from_past.shape[1]       )

										# select random slice
										lowercase_   :     Union[str, Any]									=			int(ids_tensor((1,)							,     output_from_past.shape[-1]       )       )
										lowercase_   :     List[str]									=			output_from_no_past[:, -3:, random_slice_idx]
										lowercase_   :     Any									=			output_from_past[:, :, random_slice_idx]

										# test that outputs are equal for slice
										tf.debugging.assert_near(lowercase_							,     lowercase_							,     rtol=1E-3       )




def 				lowerCamelCase      ( UpperCAmelCase__			:   List[str] , UpperCAmelCase__			:   Dict , UpperCAmelCase__			:   List[Any] , UpperCAmelCase__			:   Tuple=None , UpperCAmelCase__			:   Union[str, Any]=None , UpperCAmelCase__			:   str=None , UpperCAmelCase__			:   Any=None , UpperCAmelCase__			:   Any=None , )     -> List[Any]:
							if attention_mask is None:
														lowercase_   :     Tuple									=			tf.cast(tf.math.not_equal(UpperCAmelCase__ , config.pad_token_id					) , tf.inta					)
							if decoder_attention_mask is None:
														lowercase_   :     Optional[int]									=			tf.concat(
														    [
														        tf.ones(decoder_input_ids[:, :1].shape , dtype=tf.inta					),
														        tf.cast(tf.math.not_equal(decoder_input_ids[:, 1:] , config.pad_token_id					) , tf.inta					),
														    ] , axis=-1 , )
							if head_mask is None:
														lowercase_   :     Union[str, Any]									=			tf.ones((config.encoder_layers, config.encoder_attention_heads)					)
							if decoder_head_mask is None:
														lowercase_   :     Optional[int]									=			tf.ones((config.decoder_layers, config.decoder_attention_heads)					)
							if cross_attn_head_mask is None:
														lowercase_   :     Any									=			tf.ones((config.decoder_layers, config.decoder_attention_heads)					)
							return {
							    "input_ids": input_ids,
							    "decoder_input_ids": decoder_input_ids,
							    "attention_mask": attention_mask,
							    "decoder_attention_mask": decoder_attention_mask,
							    "head_mask": head_mask,
							    "decoder_head_mask": decoder_head_mask,
							    "cross_attn_head_mask": cross_attn_head_mask,
							}





@require_tf
class        __magic_name__		(       _UpperCAmelCase,	_UpperCAmelCase,	unittest.TestCase):
			UpperCamelCase__							=			(TFMarianMTModel, TFMarianModel) if is_tf_available() else ()
			UpperCamelCase__							=			(TFMarianMTModel,) if is_tf_available() else ()
			UpperCamelCase__							=			(
			    {
			        '''conversational''': TFMarianMTModel,
			        '''feature-extraction''': TFMarianModel,
			        '''summarization''': TFMarianMTModel,
			        '''text2text-generation''': TFMarianMTModel,
			        '''translation''': TFMarianMTModel,
			    }
			    if is_tf_available()
			    else {}
			)
			UpperCamelCase__							=			True
			UpperCamelCase__							=			False
			UpperCamelCase__							=			False







			def       SCREAMING_SNAKE_CASE_	(      self							:    Dict       ):
										lowercase_   :     Dict									=			TFMarianModelTester(self       )
										lowercase_   :     Tuple									=			ConfigTester(self							,     config_class=lowercase_       )







			def       SCREAMING_SNAKE_CASE_	(      self							:    Optional[Any]       ):
										self.config_tester.run_common_tests()







			def       SCREAMING_SNAKE_CASE_	(      self							:    Any       ):
										lowercase_   :     Dict									=			self.model_tester.prepare_config_and_inputs_for_common()
										self.model_tester.check_decoder_model_past_large_inputs(*lowercase_       )





@require_tf
class        __magic_name__		(       unittest.TestCase):
			UpperCamelCase__							=			1000  # show more chars for failing integration tests







			@classmethod
			def       SCREAMING_SNAKE_CASE_	(      cls							:    Optional[int]       ):
										lowercase_   :     Optional[Any]									=			f'''Helsinki-NLP/opus-mt-{cls.src}-{cls.tgt}'''
										return cls







			@cached_property
			def       SCREAMING_SNAKE_CASE_	(      self							:    Tuple       ):
										return AutoTokenizer.from_pretrained(self.model_name       )







			@property
			def       SCREAMING_SNAKE_CASE_	(      self							:    Tuple       ):
										return self.tokenizer.eos_token_id







			@cached_property
			def       SCREAMING_SNAKE_CASE_	(      self							:    Optional[int]       ):
										warnings.simplefilter("""error"""       )
										lowercase_   :     TFMarianMTModel									=			TFAutoModelForSeqaSeqLM.from_pretrained(self.model_name       )
										assert isinstance(lowercase_							,     lowercase_       )
										lowercase_   :     List[Any]									=			model.config
										self.assertListEqual(c.bad_words_ids							,     [[c.pad_token_id]]       )
										self.assertEqual(c.max_length							,     512       )
										self.assertEqual(c.decoder_start_token_id							,     c.pad_token_id       )
										return model







			def       SCREAMING_SNAKE_CASE_	(      self							:    Union[str, Any]							,     **lowercase_							:    str       ):
										lowercase_   :     List[Any]									=			self.translate_src_text(**lowercase_       )
										self.assertListEqual(self.expected_text							,     lowercase_       )







			def       SCREAMING_SNAKE_CASE_	(      self							:    Union[str, Any]							,     **lowercase_							:    Dict       ):
										lowercase_   :     Dict									=			self.tokenizer(self.src_text							,     **lowercase_							,     padding=lowercase_							,     return_tensors="""tf"""       )
										lowercase_   :     Tuple									=			self.model.generate(
										    model_inputs.input_ids							,     attention_mask=model_inputs.attention_mask							,     num_beams=2							,     max_length=128       )
										lowercase_   :     Any									=			self.tokenizer.batch_decode(generated_ids.numpy()							,     skip_special_tokens=lowercase_       )
										return generated_words





@require_sentencepiece
@require_tokenizers
@require_tf
class        __magic_name__		(       _UpperCAmelCase):
			UpperCamelCase__							=			'''mt'''
			UpperCamelCase__							=			'''en'''
			UpperCamelCase__							=			['''Billi messu b\'mod ġentili, Ġesù fejjaq raġel li kien milqut bil - marda kerha tal - ġdiem.''']
			UpperCamelCase__							=			['''Touching gently, Jesus healed a man who was affected by the sad disease of leprosy.''']







			@unittest.skip("""Skipping until #12647 is resolved."""       )
			@slow
			def       SCREAMING_SNAKE_CASE_	(      self							:    List[str]       ):
										self._assert_generated_batch_equal_expected()





@require_sentencepiece
@require_tokenizers
@require_tf
class        __magic_name__		(       _UpperCAmelCase):
			UpperCamelCase__							=			'''en'''
			UpperCamelCase__							=			'''zh'''
			UpperCamelCase__							=			['''My name is Wolfgang and I live in Berlin''']
			UpperCamelCase__							=			['''我叫沃尔夫冈 我住在柏林''']







			@unittest.skip("""Skipping until #12647 is resolved."""       )
			@slow
			def       SCREAMING_SNAKE_CASE_	(      self							:    str       ):
										self._assert_generated_batch_equal_expected()





@require_sentencepiece
@require_tokenizers
@require_tf
class        __magic_name__		(       _UpperCAmelCase):
			UpperCamelCase__							=			'''en'''
			UpperCamelCase__							=			'''ROMANCE'''
			UpperCamelCase__							=			[
			    '''>>fr<< Don\'t spend so much time watching TV.''',
			    '''>>pt<< Your message has been sent.''',
			    '''>>es<< He\'s two years older than me.''',
			]
			UpperCamelCase__							=			[
			    '''Ne passez pas autant de temps à regarder la télé.''',
			    '''A sua mensagem foi enviada.''',
			    '''Es dos años más viejo que yo.''',
			]







			@unittest.skip("""Skipping until #12647 is resolved."""       )
			@slow
			def       SCREAMING_SNAKE_CASE_	(      self							:    Optional[int]       ):
										self._assert_generated_batch_equal_expected()







			@unittest.skip("""Skipping until #12647 is resolved."""       )
			@slow
			def       SCREAMING_SNAKE_CASE_	(      self							:    Tuple       ):
										lowercase_   :     List[str]									=			TranslationPipeline(self.model							,     self.tokenizer							,     framework="""tf"""       )
										lowercase_   :     Optional[int]									=			pipeline(self.src_text       )
										self.assertEqual(self.expected_text							,     [x["""translation_text"""] for x in output]       )






'''simple docstring'''




from __future__ import annotations




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




def 				lowerCamelCase      ( UpperCAmelCase__			:   int					)     -> str:
							global graph, reversed_graph, scc, component, visit, stack
							if visit[u]:
														return
							lowercase_   :     Tuple									=			True
							component.append(UpperCAmelCase__					)
							for v in reversed_graph[u]:
														dfsa(UpperCAmelCase__					)




def 				lowerCamelCase      ( )     -> int:
							global graph, reversed_graph, scc, component, visit, stack
							for i in range(UpperCAmelCase__					):
														dfs(UpperCAmelCase__					)
							lowercase_   :     Optional[int]									=			[False] * n
							for i in stack[::-1]:
														if visit[i]:
																					continue
														lowercase_   :     Union[str, Any]									=			[]
														dfsa(UpperCAmelCase__					)
														scc.append(UpperCAmelCase__					)
							return scc


if __name__ == "__main__":
						# n - no of nodes, m - no of edges
						_lowercase							,			_lowercase		:					Optional[Any]													=		list(map(int, input().strip().split()))

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

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





