
'''simple docstring'''





import tempfile
import unittest

import transformers
from transformers import XGLMConfig, XGLMTokenizer, is_flax_available, is_torch_available
from transformers.testing_utils import is_pt_flax_cross_test, require_flax, require_sentencepiece, slow

from ...generation.test_flax_utils import FlaxGenerationTesterMixin
from ...test_modeling_flax_common import FlaxModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask


if is_flax_available():
 import jax
 import jax.numpy as jnp
 import numpy as np

 from transformers.modeling_flax_pytorch_utils import (
     convert_pytorch_state_dict_to_flax,
     load_flax_weights_in_pytorch_model,
 )
 from transformers.models.xglm.modeling_flax_xglm import FlaxXGLMForCausalLM, FlaxXGLMModel


if is_torch_available():
 import torch


@require_flax
class 	UpperCamelCase__					:






 def __init__(     self					:str		,			_A					:Optional[Any]		,			_A					:List[Any]=14		,			_A					:List[Any]=7		,			_A					:Union[str, Any]=True		,			_A					:List[str]=True		,			_A					:str=True		,			_A					:Any=99		,			_A					:int=32		,			_A					:Optional[int]=5		,			_A					:Any=4		,			_A					:List[str]=37		,			_A					:str="gelu"		,			_A					:int=0.1		,			_A					:Dict=0.1		,			_A					:List[Any]=512		,			_A					:Tuple=0.02		,			_A					:int=None		,			)			->     Optional[int]:







       '''simple docstring'''



       __A    		=     parent
       __A    		=     batch_size
       __A    		=     seq_length
       __A    		=     is_training
       __A    		=     use_input_mask
       __A    		=     use_labels
       __A    		=     vocab_size
       __A    		=     d_model
       __A    		=     num_hidden_layers
       __A    		=     num_attention_heads
       __A    		=     ffn_dim
       __A    		=     activation_function
       __A    		=     activation_dropout
       __A    		=     attention_dropout
       __A    		=     max_position_embeddings
       __A    		=     initializer_range
       __A    		=     None
       __A    		=     0
       __A    		=     2
       __A    		=     1






 def 		lowercase_  (     self					:Any     )			->     Optional[int]:







       '''simple docstring'''



       __A    		=     np.clip(ids_tensor([self.batch_size, self.seq_length]		,			self.vocab_size     )		,			3		,			self.vocab_size     )

       __A    		=     None
       if self.use_input_mask:
             __A    		=     random_attention_mask([self.batch_size, self.seq_length]     )

       __A    		=     XGLMConfig(
           vocab_size=self.vocab_size		,			d_model=self.hidden_size		,			num_layers=self.num_hidden_layers		,			attention_heads=self.num_attention_heads		,			ffn_dim=self.ffn_dim		,			activation_function=self.activation_function		,			activation_dropout=self.activation_dropout		,			attention_dropout=self.attention_dropout		,			max_position_embeddings=self.max_position_embeddings		,			initializer_range=self.initializer_range		,			use_cache=_A		,			bos_token_id=self.bos_token_id		,			eos_token_id=self.eos_token_id		,			pad_token_id=self.pad_token_id		,			)

       return (config, input_ids, input_mask)






 def 		lowercase_  (     self					:str     )			->     Optional[Any]:







       '''simple docstring'''



       __A    		=     self.prepare_config_and_inputs()
       __A		, __A		, __A    		=     config_and_inputs
       __A    		=     {'input_ids': input_ids, 'attention_mask': attention_mask}
       return config, inputs_dict






 def 		lowercase_  (     self					:Dict     )			->     Dict:







       '''simple docstring'''



       __A		, __A		, __A    		=     self.prepare_config_and_inputs()

       __A    		=     floats_tensor([self.batch_size, self.seq_length, self.hidden_size]     )
       __A    		=     ids_tensor([self.batch_size, self.seq_length]		,			vocab_size=2     )

       return (
           config,
           input_ids,
           attention_mask,
           encoder_hidden_states,
           encoder_attention_mask,
       )






 def 		lowercase_  (     self					:Optional[Any]		,			_A					:List[Any]		,			_A					:Tuple		,			_A					:Tuple		,			_A					:int     )			->     Optional[Any]:







       '''simple docstring'''



       __A    		=     20
       __A    		=     model_class_name(_A     )

       __A    		=     model.init_cache(input_ids.shape[0]		,			_A     )
       __A    		=     jnp.ones((input_ids.shape[0], max_decoder_length)		,			dtype='i4'     )

       __A    		=     jnp.broadcast_to(
           jnp.arange(input_ids.shape[-1] - 1     )[None, :]		,			(input_ids.shape[0], input_ids.shape[-1] - 1)     )
       __A    		=     model(
           input_ids[:, :-1]		,			attention_mask=_A		,			past_key_values=_A		,			position_ids=_A		,			)

       __A    		=     jnp.array(input_ids.shape[0] * [[input_ids.shape[-1] - 1]]		,			dtype='i4'     )
       __A    		=     model(
           input_ids[:, -1:]		,			attention_mask=_A		,			past_key_values=outputs_cache.past_key_values		,			position_ids=_A		,			)

       __A    		=     model(_A     )

       __A    		=     np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])     )     )
       self.parent.assertTrue(diff < 1E-3		,			msg=F'Max diff is {diff}'     )






 def 		lowercase_  (     self					:Optional[int]		,			_A					:List[str]		,			_A					:List[str]		,			_A					:Tuple		,			_A					:Optional[Any]     )			->     Union[str, Any]:







       '''simple docstring'''



       __A    		=     20
       __A    		=     model_class_name(_A     )

       __A    		=     jnp.concatenate(
           [attention_mask, jnp.zeros((attention_mask.shape[0], max_decoder_length - attention_mask.shape[1])     )]		,			axis=-1		,			)

       __A    		=     model.init_cache(input_ids.shape[0]		,			_A     )
       __A    		=     jnp.broadcast_to(
           jnp.arange(input_ids.shape[-1] - 1     )[None, :]		,			(input_ids.shape[0], input_ids.shape[-1] - 1)     )

       __A    		=     model(
           input_ids[:, :-1]		,			attention_mask=_A		,			past_key_values=_A		,			position_ids=_A		,			)
       __A    		=     jnp.array(input_ids.shape[0] * [[input_ids.shape[-1] - 1]]		,			dtype='i4'     )
       __A    		=     model(
           input_ids[:, -1:]		,			past_key_values=outputs_cache.past_key_values		,			attention_mask=_A		,			position_ids=_A		,			)

       __A    		=     model(_A		,			attention_mask=_A     )
       __A    		=     np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])     )     )
       self.parent.assertTrue(diff < 1E-3		,			msg=F'Max diff is {diff}'     )


@require_sentencepiece
@require_flax
class 	UpperCamelCase__					(      SCREAMING_SNAKE_CASE ,       SCREAMING_SNAKE_CASE ,       unittest.TestCase):
 UpperCAmelCase__      :      int  			=   (FlaxXGLMModel, FlaxXGLMForCausalLM) if is_flax_available() else ()
 UpperCAmelCase__      :      Optional[Any]  			=   (FlaxXGLMForCausalLM,) if is_flax_available() else ()






 def 		lowercase_  (     self					:List[Any]     )			->     List[str]:







       '''simple docstring'''



       __A    		=     FlaxXGLMModelTester(self     )






 def 		lowercase_  (     self					:Any     )			->     Tuple:







       '''simple docstring'''



       for model_class_name in self.all_model_classes:
             __A		, __A		, __A    		=     self.model_tester.prepare_config_and_inputs()
             self.model_tester.check_use_cache_forward(_A		,			_A		,			_A		,			_A     )






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







       '''simple docstring'''



       for model_class_name in self.all_model_classes:
             __A		, __A		, __A    		=     self.model_tester.prepare_config_and_inputs()
             self.model_tester.check_use_cache_forward_with_attn_mask(
                 _A		,			_A		,			_A		,			_A     )






 @slow
 def 		lowercase_  (     self					:Optional[int]     )			->     List[Any]:







       '''simple docstring'''



       __A    		=     XGLMTokenizer.from_pretrained('XGLM'		,			padding_side='left'     )
       __A    		=     tokenizer(['Hello this is a long string', 'Hey']		,			return_tensors='np'		,			padding=_A		,			truncation=_A     )

       __A    		=     FlaxXGLMForCausalLM.from_pretrained('facebook/xglm-564M'     )
       __A    		=     1
       __A    		=     False

       __A    		=     jax.jit(model.generate     )

       __A    		=     jit_generate(inputs['input_ids']		,			attention_mask=inputs['attention_mask']     ).sequences

       __A    		=     tokenizer.batch_decode(_A		,			skip_special_tokens=_A     )

       __A    		=     [
           'Hello this is a long string of questions, but I\'m not sure if I\'m',
           'Hey, I\'m a newbie to the forum and I\'',
       ]

       self.assertListEqual(_A		,			_A     )






 @is_pt_flax_cross_test
 def 		lowercase_  (     self					:Dict     )			->     int:







       '''simple docstring'''



       __A		, __A    		=     self.model_tester.prepare_config_and_inputs_for_common()

       for model_class in self.all_model_classes:
             with self.subTest(model_class.__name__     ):
                   # prepare inputs
                   __A    		=     self._prepare_for_class(_A		,			_A     )
                   __A    		=     {k: torch.tensor(v.tolist()     ) for k, v in prepared_inputs_dict.items()}

                   # load corresponding PyTorch class
                   __A    		=     model_class.__name__[4:]  # Skip the "Flax" at the beginning
                   __A    		=     getattr(_A		,			_A     )

                   __A		, __A    		=     pt_inputs['input_ids'].shape
                   __A    		=     np.random.randint(0		,			seq_length - 1		,			size=(batch_size,)     )
                   for batch_idx, start_index in enumerate(_A     ):
                         __A    		=     0
                         __A    		=     1
                         __A    		=     0
                         __A    		=     1
                   __A    		=     pt_model_class(_A     ).eval()
                   # Flax models don't use the `use_cache` option and cache is not returned as a default.
                   # So we disable `use_cache` here for PyTorch model.
                   __A    		=     False
                   __A    		=     model_class(_A		,			dtype=jnp.floataa     )
                   __A    		=     convert_pytorch_state_dict_to_flax(pt_model.state_dict()		,			_A     )
                   __A    		=     fx_state

                   with torch.no_grad():
                         __A    		=     pt_model(**_A     ).to_tuple()

                   __A    		=     fx_model(**_A     ).to_tuple()
                   self.assertEqual(len(_A     )		,			len(_A     )		,			'Output lengths differ between Flax and PyTorch'     )
                   for fx_output, pt_output in zip(_A		,			_A     ):
                         self.assert_almost_equals(fx_output[:, -1]		,			pt_output[:, -1].numpy()		,			4E-2     )

                   with tempfile.TemporaryDirectory() as tmpdirname:
                         pt_model.save_pretrained(_A     )
                         __A    		=     model_class.from_pretrained(_A		,			from_pt=_A     )

                   __A    		=     fx_model_loaded(**_A     ).to_tuple()
                   self.assertEqual(
                       len(_A     )		,			len(_A     )		,			'Output lengths differ between Flax and PyTorch'     )
                   for fx_output_loaded, pt_output in zip(_A		,			_A     ):
                         self.assert_almost_equals(fx_output_loaded[:, -1]		,			pt_output[:, -1].numpy()		,			4E-2     )






 @is_pt_flax_cross_test
 def 		lowercase_  (     self					:str     )			->     List[str]:







       '''simple docstring'''



       __A		, __A    		=     self.model_tester.prepare_config_and_inputs_for_common()
       for model_class in self.all_model_classes:
             with self.subTest(model_class.__name__     ):
                   # prepare inputs
                   __A    		=     self._prepare_for_class(_A		,			_A     )
                   __A    		=     {k: torch.tensor(v.tolist()     ) for k, v in prepared_inputs_dict.items()}

                   # load corresponding PyTorch class
                   __A    		=     model_class.__name__[4:]  # Skip the "Flax" at the beginning
                   __A    		=     getattr(_A		,			_A     )

                   __A    		=     pt_model_class(_A     ).eval()
                   __A    		=     False
                   __A    		=     model_class(_A		,			dtype=jnp.floataa     )

                   __A    		=     load_flax_weights_in_pytorch_model(_A		,			fx_model.params     )
                   __A		, __A    		=     pt_inputs['input_ids'].shape
                   __A    		=     np.random.randint(0		,			seq_length - 1		,			size=(batch_size,)     )
                   for batch_idx, start_index in enumerate(_A     ):
                         __A    		=     0
                         __A    		=     1
                         __A    		=     0
                         __A    		=     1

                   # make sure weights are tied in PyTorch
                   pt_model.tie_weights()

                   with torch.no_grad():
                         __A    		=     pt_model(**_A     ).to_tuple()

                   __A    		=     fx_model(**_A     ).to_tuple()
                   self.assertEqual(len(_A     )		,			len(_A     )		,			'Output lengths differ between Flax and PyTorch'     )
                   for fx_output, pt_output in zip(_A		,			_A     ):
                         self.assert_almost_equals(fx_output[:, -1]		,			pt_output[:, -1].numpy()		,			4E-2     )

                   with tempfile.TemporaryDirectory() as tmpdirname:
                         fx_model.save_pretrained(_A     )
                         __A    		=     pt_model_class.from_pretrained(_A		,			from_flax=_A     )

                   with torch.no_grad():
                         __A    		=     pt_model_loaded(**_A     ).to_tuple()

                   self.assertEqual(
                       len(_A     )		,			len(_A     )		,			'Output lengths differ between Flax and PyTorch'     )
                   for fx_output, pt_output in zip(_A		,			_A     ):
                         self.assert_almost_equals(fx_output[:, -1]		,			pt_output[:, -1].numpy()		,			4E-2     )






 @slow
 def 		lowercase_  (     self					:List[Any]     )			->     Tuple:







       '''simple docstring'''



       for model_class_name in self.all_model_classes:
             __A    		=     model_class_name.from_pretrained('facebook/xglm-564M'     )
             __A    		=     model(np.ones((1, 1)     )     )
             self.assertIsNotNone(_A     )








'''simple docstring'''





from __future__ import annotations





def     snake_case							(						UpperCAmelCase		)->     List[Any]:







      """simple docstring"""
      global graph, reversed_graph, scc, component, visit, stack
      if visit[u]:
            return
      __A    		=     True
      for v in graph[u]:
            dfs(UpperCAmelCase		)
      stack.append(UpperCAmelCase		)





def     snake_case							(						UpperCAmelCase		)->     List[Any]:







      """simple docstring"""
      global graph, reversed_graph, scc, component, visit, stack
      if visit[u]:
            return
      __A    		=     True
      component.append(UpperCAmelCase		)
      for v in reversed_graph[u]:
            dfsa(UpperCAmelCase		)





def     snake_case							(						)->     Any:







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


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

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

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






