




'''simple docstring'''
from typing import List

from packaging import version
from sklearn.metrics import fa_score

import datasets
from datasets.config import PY_VERSION


if PY_VERSION < version.parse("3.8"):
							import importlib_metadata
else:
							import importlib.metadata as importlib_metadata


# TODO(Patrick/Anton)
_SCREAMING_SNAKE_CASE =	"\\n"

_SCREAMING_SNAKE_CASE =	"\\n    XTREME-S is a benchmark to evaluate universal cross-lingual speech representations in many languages.\n    XTREME-S covers four task families: speech recognition, classification, speech-to-text translation and retrieval.\n"

_SCREAMING_SNAKE_CASE =	"\nCompute XTREME-S evaluation metric associated to each XTREME-S dataset.\nArgs:\n    predictions: list of predictions to score.\n        Each translation should be tokenized into a list of tokens.\n    references: list of lists of references for each translation.\n        Each reference should be tokenized into a list of tokens.\n    bleu_kwargs: optional dict of keywords to be passed when computing 'bleu'.\n        Keywords include Dict can be one of 'smooth_method', 'smooth_value', 'force', 'lowercase',\n        'tokenize', 'use_effective_order'.\n    wer_kwargs: optional dict of keywords to be passed when computing 'wer' and 'cer'.\n        Keywords include 'concatenate_texts'.\nReturns: depending on the XTREME-S task, one or several of:\n    \"accuracy\": Accuracy - for 'fleurs-lang_id', 'minds14'\n    \"f1\": F1 score - for 'minds14'\n    \"wer\": Word error rate - for 'mls', 'fleurs-asr', 'voxpopuli', 'babel'\n    \"cer\": Character error rate - for 'mls', 'fleurs-asr', 'voxpopuli', 'babel'\n    \"bleu\": BLEU score according to the `sacrebleu` metric - for 'covost2'\nExamples:\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'mls')  # 'mls', 'voxpopuli', 'fleurs-asr' or 'babel'\n    >>> references = [\"it is sunny here\", \"paper and pen are essentials\"]\n    >>> predictions = [\"it's sunny\", \"paper pen are essential\"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'wer': 0.56, 'cer': 0.27}\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'covost2')\n    >>> references = [\"bonjour paris\", \"il est necessaire de faire du sport de temps en temp\"]\n    >>> predictions = [\"bonjour paris\", \"il est important de faire du sport souvent\"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'bleu': 31.65}\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'fleurs-lang_id')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'accuracy': 0.6}\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'minds14')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'f1': 0.58, 'accuracy': 0.6}\n"

_SCREAMING_SNAKE_CASE =	["fleurs-asr", "mls", "voxpopuli", "babel", "covost2", "fleurs-lang_id", "minds14"]
_SCREAMING_SNAKE_CASE =	""

try:
							from jiwer import transforms as tr

							_SCREAMING_SNAKE_CASE =	True
except ImportError:
							_SCREAMING_SNAKE_CASE =	False

if _jiwer_available and version.parse(importlib_metadata.version("jiwer")) < version.parse("2.3.0"):
							class      __UpperCAmelCase							(    tr.AbstractTransform							):



												'''simple docstring'''





												def __init__(  self    :	Any			,					_lowercase    :	str = " ")						->       Dict:
															A_       		=   sentence_delimiter



												def 						__snake_case	(  self    :	List[str]			,					_lowercase    :	str)						->       Any:
															return list(_lowercase)



												def 						__snake_case	(  self    :	List[str]			,					_lowercase    :	List[str])						->       Dict:
															A_       		=   []
															for sent_idx, sentence in enumerate(_lowercase):
																		chars.extend(self.process_string(_lowercase))
																		if self.sentence_delimiter is not None and self.sentence_delimiter != "" and sent_idx < len(_lowercase) - 1:
																					chars.append(self.sentence_delimiter)
															return chars





							_SCREAMING_SNAKE_CASE =	tr.Compose(
							    [tr.RemoveMultipleSpaces(), tr.Strip(), SentencesToListOfCharacters(SENTENCE_DELIMITER)]
							)
elif _jiwer_available:
							_SCREAMING_SNAKE_CASE =	tr.Compose(
							    [
							        tr.RemoveMultipleSpaces(),
							        tr.Strip(),
							        tr.ReduceToSingleSentence(SENTENCE_DELIMITER),
							        tr.ReduceToListOfListOfChars(),
							    ]
							)
else:
							_SCREAMING_SNAKE_CASE =	None





def  lowerCamelCase(       SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    )		->		Any:
			return float((preds == labels).mean()    )





def  lowerCamelCase(       SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    )		->		Optional[int]:
			return {
			    "f1": float(fa_score(y_true=SCREAMING_SNAKE_CASE_					,y_pred=SCREAMING_SNAKE_CASE_					,average='macro'    )    ),
			    "accuracy": simple_accuracy(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    ),
			}





def  lowerCamelCase(       SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_="exp"					,SCREAMING_SNAKE_CASE_=None					,SCREAMING_SNAKE_CASE_=False					,SCREAMING_SNAKE_CASE_=False					,SCREAMING_SNAKE_CASE_=None					,SCREAMING_SNAKE_CASE_=False					,)		->		Dict:
			# xtreme-s can only have one label
			A_       		=   [[label] for label in labels]
			A_       		=   list(SCREAMING_SNAKE_CASE_    )
			try:
						import sacrebleu as scb
			except ImportError:
						raise ValueError(
						    'sacrebleu has to be installed in order to apply the bleu metric for covost2.'
						    'You can install it via `pip install sacrebleu`.'    )

			if version.parse(scb.__version__    ) < version.parse('1.4.12'    ):
						raise ImportWarning(
						    'To use `sacrebleu`, the module `sacrebleu>=1.4.12` is required, and the current version of `sacrebleu` doesn\'t match this condition.\n'
						    'You can install it with `pip install "sacrebleu>=1.4.12"`.'    )

			A_       		=   len(labels[0]    )
			if any(len(SCREAMING_SNAKE_CASE_    ) != references_per_prediction for refs in labels    ):
						raise ValueError('Sacrebleu requires the same number of references for each prediction'    )
			A_       		=   [[refs[i] for refs in labels] for i in range(SCREAMING_SNAKE_CASE_    )]
			A_       		=   scb.corpus_bleu(
			    SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,smooth_method=SCREAMING_SNAKE_CASE_					,smooth_value=SCREAMING_SNAKE_CASE_					,force=SCREAMING_SNAKE_CASE_					,lowercase=SCREAMING_SNAKE_CASE_					,use_effective_order=SCREAMING_SNAKE_CASE_					,**({'tokenize': tokenize} if tokenize else {})					,)
			return {"bleu": output.score}





def  lowerCamelCase(       SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    )		->		Optional[int]:
			try:
						from jiwer import compute_measures
			except ImportError:
						raise ValueError(
						    F'jiwer has to be installed in order to apply the wer metric for {config_name}.'
						    'You can install it via `pip install jiwer`.'    )

			if concatenate_texts:
						A_       		=   compute_measures(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    )['wer']

						A_       		=   compute_measures(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,truth_transform=SCREAMING_SNAKE_CASE_					,hypothesis_transform=SCREAMING_SNAKE_CASE_    )['wer']
						return {"wer": wer, "cer": cer}
			else:

						def compute_score(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_="wer"    ):
									A_       		=   0
									A_       		=   0
									for prediction, reference in zip(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    ):
												if score_type == "wer":
															A_       		=   compute_measures(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_    )
												elif score_type == "cer":
															A_       		=   compute_measures(
															    SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,truth_transform=SCREAMING_SNAKE_CASE_					,hypothesis_transform=SCREAMING_SNAKE_CASE_    )
												incorrect += measures["substitutions"] + measures["deletions"] + measures["insertions"]
												total += measures["substitutions"] + measures["deletions"] + measures["hits"]
									return incorrect / total

						return {"wer": compute_score(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,'wer'    ), "cer": compute_score(SCREAMING_SNAKE_CASE_					,SCREAMING_SNAKE_CASE_					,'cer'    )}






@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION ,_KWARGS_DESCRIPTION							)
class      __UpperCAmelCase							(    datasets.Metric							):



					'''simple docstring'''





					def 						__snake_case	(  self    :	Union[str, Any])						->       List[Any]:
								if self.config_name not in _CONFIG_NAMES:
											raise KeyError(F'You should supply a configuration name selected in {_CONFIG_NAMES}')

								A_       		=   'int64' if self.config_name in ['fleurs-lang_id', 'minds14'] else 'string'

								return datasets.MetricInfo(
								    description=_DESCRIPTION			,					citation=_CITATION			,					inputs_description=_KWARGS_DESCRIPTION			,					features=datasets.Features(
								        {'predictions': datasets.Value(_lowercase), 'references': datasets.Value(_lowercase)})			,					codebase_urls=[]			,					reference_urls=[]			,					format='numpy'			,					)



					def 						__snake_case	(  self    :	str			,					_lowercase    :	Optional[int]			,					_lowercase    :	Any			,					_lowercase    :	Dict=None			,					_lowercase    :	str=None)						->       str:
								A_       		=   bleu_kwargs if bleu_kwargs is not None else {}
								A_       		=   wer_kwargs if wer_kwargs is not None else {}

								if self.config_name == "fleurs-lang_id":
											return {"accuracy": simple_accuracy(_lowercase			,					_lowercase)}
								elif self.config_name == "minds14":
											return fa_and_simple_accuracy(_lowercase			,					_lowercase)
								elif self.config_name == "covost2":
											A_       		=   bleu_kwargs.pop('smooth_method'			,					'exp')
											A_       		=   bleu_kwargs.pop('smooth_value'			,					_lowercase)
											A_       		=   bleu_kwargs.pop('force'			,					_lowercase)
											A_       		=   bleu_kwargs.pop('lowercase'			,					_lowercase)
											A_       		=   bleu_kwargs.pop('tokenize'			,					_lowercase)
											A_       		=   bleu_kwargs.pop('use_effective_order'			,					_lowercase)
											return bleu(
											    preds=_lowercase			,					labels=_lowercase			,					smooth_method=_lowercase			,					smooth_value=_lowercase			,					force=_lowercase			,					lowercase=_lowercase			,					tokenize=_lowercase			,					use_effective_order=_lowercase			,					)
								elif self.config_name in ["fleurs-asr", "mls", "voxpopuli", "babel"]:
											A_       		=   wer_kwargs.pop('concatenate_texts'			,					_lowercase)
											return wer_and_cer(_lowercase			,					_lowercase			,					_lowercase			,					self.config_name)
								else:
											raise KeyError(F'You should supply a configuration name selected in {_CONFIG_NAMES}')










'''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())




