from collections import OrderedDict
from typing import Any, Mapping, Optional

from ... import PreTrainedTokenizer
from ...configuration_utils import PretrainedConfig
from ...file_utils import TensorType, is_torch_available
from ...onnx import OnnxConfig, OnnxConfigWithPast, OnnxSeqaSeqConfigWithPast
from ...onnx.utils import compute_effective_axis_dimension
from ...utils import logging


_SCREAMING_SNAKE_CASE   		=			logging.get_logger(__name__)

_SCREAMING_SNAKE_CASE   		=			{
    """facebook/blenderbot-3B""": """https://huggingface.co/facebook/blenderbot-3B/resolve/main/config.json""",
    # See all Blenderbot models at https://huggingface.co/models?filter=blenderbot
}
class SCREAMING_SNAKE_CASE_		(			__lowerCAmelCase		):
   __lowerCAmelCase											=							"""blenderbot"""
   __lowerCAmelCase											=							["""past_key_values"""]
   __lowerCAmelCase											=							{"""num_attention_heads""": """encoder_attention_heads""", """hidden_size""": """d_model"""}







   def __init__(    self	:	Tuple      ,      lowerCamelCase_	:	List[Any]=8008      ,      lowerCamelCase_	:	Union[str, Any]=128      ,      lowerCamelCase_	:	List[Any]=2      ,      lowerCamelCase_	:	Union[str, Any]=1_0240      ,      lowerCamelCase_	:	List[Any]=32      ,      lowerCamelCase_	:	Optional[int]=24      ,      lowerCamelCase_	:	str=1_0240      ,      lowerCamelCase_	:	Optional[int]=32      ,      lowerCamelCase_	:	int=0.0      ,      lowerCamelCase_	:	Optional[Any]=0.0      ,      lowerCamelCase_	:	List[Any]=True      ,      lowerCamelCase_	:	str=True      ,      lowerCamelCase_	:	int="gelu"      ,      lowerCamelCase_	:	int=2560      ,      lowerCamelCase_	:	str=0.1      ,      lowerCamelCase_	:	str=0.0      ,      lowerCamelCase_	:	Optional[int]=0.0      ,      lowerCamelCase_	:	Optional[Any]=0.0_2      ,      lowerCamelCase_	:	List[Any]=1      ,      lowerCamelCase_	:	Dict=False      ,      lowerCamelCase_	:	Tuple=0      ,      lowerCamelCase_	:	List[str]=1      ,      lowerCamelCase_	:	str=2      ,      lowerCamelCase_	:	Union[str, Any]=3      ,      lowerCamelCase_	:	List[str]=2      ,      **lowerCamelCase_	:	Dict      ,      ):





    """simple docstring"""


    UpperCamelCase      =			vocab_size
    UpperCamelCase      =			max_position_embeddings
    UpperCamelCase      =			d_model
    UpperCamelCase      =			encoder_ffn_dim
    UpperCamelCase      =			encoder_layers
    UpperCamelCase      =			encoder_attention_heads
    UpperCamelCase      =			decoder_ffn_dim
    UpperCamelCase      =			decoder_layers
    UpperCamelCase      =			decoder_attention_heads
    UpperCamelCase      =			dropout
    UpperCamelCase      =			attention_dropout
    UpperCamelCase      =			activation_dropout
    UpperCamelCase      =			activation_function
    UpperCamelCase      =			init_std
    UpperCamelCase      =			encoder_layerdrop
    UpperCamelCase      =			decoder_layerdrop
    UpperCamelCase      =			use_cache
    UpperCamelCase      =			encoder_layers
    UpperCamelCase      =			scale_embedding  # scale factor will be sqrt(d_model) if True

    super().__init__(
        pad_token_id=lowerCamelCase_      ,      bos_token_id=lowerCamelCase_      ,      eos_token_id=lowerCamelCase_      ,      is_encoder_decoder=lowerCamelCase_      ,      decoder_start_token_id=lowerCamelCase_      ,      encoder_no_repeat_ngram_size=lowerCamelCase_      ,      forced_eos_token_id=lowerCamelCase_      ,      **lowerCamelCase_      ,      )





class SCREAMING_SNAKE_CASE_		(			__lowerCAmelCase		):







   @property
   def 	lowerCamelCase_  (    self	:	str							):





    """simple docstring"""


    if self.task in ["default", "seq2seq-lm"]:
     UpperCamelCase      =			OrderedDict(
         [
             ("""input_ids""", {0: """batch""", 1: """encoder_sequence"""}),
             ("""attention_mask""", {0: """batch""", 1: """encoder_sequence"""}),
         ]							)
     if self.use_past:
      UpperCamelCase      =			{0: """batch"""}
      UpperCamelCase      =			{0: """batch""", 1: """past_decoder_sequence + sequence"""}
     else:
      UpperCamelCase      =			{0: """batch""", 1: """decoder_sequence"""}
      UpperCamelCase      =			{0: """batch""", 1: """decoder_sequence"""}
     if self.use_past:
      self.fill_with_past_key_values_(lowerCamelCase_      ,      direction="""inputs"""							)
    elif self.task == "causal-lm":
     UpperCamelCase      =			OrderedDict(
         [
             ("""input_ids""", {0: """batch""", 1: """encoder_sequence"""}),
             ("""attention_mask""", {0: """batch""", 1: """encoder_sequence"""}),
         ]							)
     if self.use_past:
      UpperCamelCase     ,    UpperCamelCase      =			self.num_layers
      for i in range(lowerCamelCase_							):
       UpperCamelCase      =			{0: """batch""", 2: """past_sequence + sequence"""}
       UpperCamelCase      =			{0: """batch""", 2: """past_sequence + sequence"""}
    else:
     UpperCamelCase      =			OrderedDict(
         [
             ("""input_ids""", {0: """batch""", 1: """encoder_sequence"""}),
             ("""attention_mask""", {0: """batch""", 1: """encoder_sequence"""}),
             ("""decoder_input_ids""", {0: """batch""", 1: """decoder_sequence"""}),
             ("""decoder_attention_mask""", {0: """batch""", 1: """decoder_sequence"""}),
         ]							)

    return common_inputs







   @property
   # Copied from transformers.models.bart.configuration_bart.BartOnnxConfig.outputs
   def 	lowerCamelCase_  (    self	:	Union[str, Any]							):





    """simple docstring"""


    if self.task in ["default", "seq2seq-lm"]:
     UpperCamelCase      =			super().outputs
    else:
     UpperCamelCase      =			super(lowerCamelCase_      ,      self							).outputs
     if self.use_past:
      UpperCamelCase     ,    UpperCamelCase      =			self.num_layers
      for i in range(lowerCamelCase_							):
       UpperCamelCase      =			{0: """batch""", 2: """past_sequence + sequence"""}
       UpperCamelCase      =			{0: """batch""", 2: """past_sequence + sequence"""}
    return common_outputs







   def 	lowerCamelCase_  (    self	:	Optional[int]      ,      lowerCamelCase_	:	PreTrainedTokenizer      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	bool = False      ,      lowerCamelCase_	:	Optional[TensorType] = None      ,      ):





    """simple docstring"""


    UpperCamelCase      =			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
        lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_							)
    # Generate decoder inputs
    UpperCamelCase      =			seq_length if not self.use_past else 1
    UpperCamelCase      =			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
        lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_							)
    UpperCamelCase      =			{f"""decoder_{name}""": tensor for name, tensor in decoder_inputs.items()}
    UpperCamelCase      =			dict(**lowerCamelCase_      ,      **lowerCamelCase_							)

    if self.use_past:
     if not is_torch_available():
      raise ValueError("""Cannot generate dummy past_keys inputs without PyTorch installed."""							)
     else:
      import torch
     UpperCamelCase     ,    UpperCamelCase      =			common_inputs["""input_ids"""].shape
     UpperCamelCase      =			common_inputs["""decoder_input_ids"""].shape[1]
     UpperCamelCase     ,    UpperCamelCase      =			self.num_attention_heads
     UpperCamelCase      =			(
         batch,
         num_encoder_attention_heads,
         encoder_seq_length,
         self._config.hidden_size // num_encoder_attention_heads,
     )
     UpperCamelCase      =			decoder_seq_length
     UpperCamelCase      =			(
         batch,
         num_decoder_attention_heads,
         decoder_past_length,
         self._config.hidden_size // num_decoder_attention_heads,
     )
     UpperCamelCase      =			torch.cat(
         [common_inputs["""decoder_attention_mask"""], torch.ones(lowerCamelCase_      ,      lowerCamelCase_							)]      ,      dim=1							)
     UpperCamelCase      =			[]
     UpperCamelCase     ,    UpperCamelCase      =			self.num_layers

     for _ in range(lowerCamelCase_							):
      common_inputs["past_key_values"].append(
          (
              torch.zeros(lowerCamelCase_							),
              torch.zeros(lowerCamelCase_							),
              torch.zeros(lowerCamelCase_							),
              torch.zeros(lowerCamelCase_							),
          )							)
    return common_inputs







   def 	lowerCamelCase_  (    self	:	List[Any]      ,      lowerCamelCase_	:	PreTrainedTokenizer      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	bool = False      ,      lowerCamelCase_	:	Optional[TensorType] = None      ,      ):





    """simple docstring"""


    UpperCamelCase      =			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
        lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_							)

    if self.use_past:
     if not is_torch_available():
      raise ValueError("""Cannot generate dummy past_keys inputs without PyTorch installed."""							)
     else:
      import torch
     UpperCamelCase     ,    UpperCamelCase      =			common_inputs["""input_ids"""].shape
     UpperCamelCase      =			seqlen
     UpperCamelCase     ,    UpperCamelCase      =			self.num_layers
     UpperCamelCase     ,    UpperCamelCase      =			self.num_attention_heads
     UpperCamelCase      =			(
         batch,
         num_encoder_attention_heads,
         past_key_values_length,
         self._config.hidden_size // num_encoder_attention_heads,
     )
     UpperCamelCase      =			common_inputs["""attention_mask"""].dtype
     UpperCamelCase      =			torch.cat(
         [common_inputs["""attention_mask"""], torch.ones(lowerCamelCase_      ,      lowerCamelCase_      ,      dtype=lowerCamelCase_							)]      ,      dim=1							)
     UpperCamelCase      =			[
         (torch.zeros(lowerCamelCase_							), torch.zeros(lowerCamelCase_							)) for _ in range(lowerCamelCase_							)
     ]
    return common_inputs







   def 	lowerCamelCase_  (    self	:	Optional[int]      ,      lowerCamelCase_	:	PreTrainedTokenizer      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	bool = False      ,      lowerCamelCase_	:	Optional[TensorType] = None      ,      ):





    """simple docstring"""


    UpperCamelCase      =			compute_effective_axis_dimension(
        lowerCamelCase_      ,      fixed_dimension=OnnxConfig.default_fixed_batch      ,      num_token_to_add=0							)

    # If dynamic axis (-1) we forward with a fixed dimension of 8 tokens to avoid optimizations made by ONNX
    UpperCamelCase      =			tokenizer.num_special_tokens_to_add(lowerCamelCase_							)
    UpperCamelCase      =			compute_effective_axis_dimension(
        lowerCamelCase_      ,      fixed_dimension=OnnxConfig.default_fixed_sequence      ,      num_token_to_add=lowerCamelCase_							)

    # Generate dummy inputs according to compute batch and sequence
    UpperCamelCase      =			[""" """.join([tokenizer.unk_token]							) * seq_length] * batch_size
    UpperCamelCase      =			dict(tokenizer(lowerCamelCase_      ,      return_tensors=lowerCamelCase_							)							)
    return common_inputs







   def 	lowerCamelCase_  (    self	:	Union[str, Any]      ,      lowerCamelCase_	:	PreTrainedTokenizer      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	int = -1      ,      lowerCamelCase_	:	bool = False      ,      lowerCamelCase_	:	Optional[TensorType] = None      ,      ):





    """simple docstring"""


    if self.task in ["default", "seq2seq-lm"]:
     UpperCamelCase      =			self._generate_dummy_inputs_for_default_and_seqaseq_lm(
         lowerCamelCase_      ,      batch_size=lowerCamelCase_      ,      seq_length=lowerCamelCase_      ,      is_pair=lowerCamelCase_      ,      framework=lowerCamelCase_							)

    elif self.task == "causal-lm":
     UpperCamelCase      =			self._generate_dummy_inputs_for_causal_lm(
         lowerCamelCase_      ,      batch_size=lowerCamelCase_      ,      seq_length=lowerCamelCase_      ,      is_pair=lowerCamelCase_      ,      framework=lowerCamelCase_							)
    else:
     UpperCamelCase      =			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
         lowerCamelCase_      ,      batch_size=lowerCamelCase_      ,      seq_length=lowerCamelCase_      ,      is_pair=lowerCamelCase_      ,      framework=lowerCamelCase_							)

    return common_inputs







   def 	lowerCamelCase_  (    self	:	List[str]      ,      lowerCamelCase_	:	List[Any]      ,      lowerCamelCase_	:	List[str]      ,      lowerCamelCase_	:	Dict      ,      lowerCamelCase_	:	Union[str, Any]							):





    """simple docstring"""


    if self.task in ["default", "seq2seq-lm"]:
     UpperCamelCase      =			super()._flatten_past_key_values_(lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_							)
    else:
     UpperCamelCase      =			super(lowerCamelCase_      ,      self							)._flatten_past_key_values_(
         lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_      ,      lowerCamelCase_							)







   def 	lowerCamelCase_  (    self	:	List[Any]      ,      lowerCamelCase_	:	Mapping[str, Mapping[int, str]]      ,      lowerCamelCase_	:	str							):





    """simple docstring"""


    if direction not in ["inputs", "outputs"]:
     raise ValueError(f"""direction must either be \"inputs\" or \"outputs\", but {direction} was given"""							)

    UpperCamelCase      =			"""past_key_values""" if direction == """inputs""" else """present"""
    UpperCamelCase     ,    UpperCamelCase      =			self.num_layers

    UpperCamelCase      =			"""past_encoder_sequence"""
    UpperCamelCase      =			"""past_decoder_sequence""" if direction == """inputs""" else """past_decoder_sequence + sequence"""

    for i in range(lowerCamelCase_							):
     UpperCamelCase      =			{0: """batch""", 2: decoder_sequence}
     UpperCamelCase      =			{0: """batch""", 2: decoder_sequence}
     UpperCamelCase      =			{0: """batch""", 2: encoder_sequence}
     UpperCamelCase      =			{0: """batch""", 2: encoder_sequence}

from __future__ import annotations





def  lowercase(  UpperCamelCase_					)		->  Dict:







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





def  lowercase(  UpperCamelCase_					)		->  Optional[int]:







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





def  lowercase(  )		->  Any:







 '''simple docstring'''
 global graph, reversed_graph, scc, component, visit, stack
 for i in range(UpperCamelCase_					):
  dfs(UpperCamelCase_					)
 UpperCamelCase      =			[False] * n
 for i in stack[::-1]:
  if visit[i]:
   continue
  UpperCamelCase      =			[]
  dfsa(UpperCamelCase_					)
  scc.append(UpperCamelCase_					)
 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())
