
import inspect
from typing import List, Optional, Union

import torch
from torch import nn
from torch.nn import functional as F
from torchvision import transforms
from transformers import CLIPImageProcessor, CLIPModel, CLIPTextModel, CLIPTokenizer

from diffusers import (
    AutoencoderKL,
    DDIMScheduler,
    DiffusionPipeline,
    DPMSolverMultistepScheduler,
    LMSDiscreteScheduler,
    PNDMScheduler,
    UNetaDConditionModel,
)
from diffusers.pipelines.stable_diffusion.pipeline_stable_diffusion import StableDiffusionPipelineOutput






class 	__magic_name__				(       nn.Module							):






     def __init__(							self		,	_lowercase		,	_lowercase=1.0  )->    str:
         super().__init__()

         UpperCamelCase_      =	cut_size
         UpperCamelCase_      =	cut_power






     def   UpperCAmelCase_							(							self		,	_lowercase		,	_lowercase  )->    str:
         UpperCamelCase_     ,					UpperCamelCase_      =	pixel_values.shape[2:4]
         UpperCamelCase_      =	min(_lowercase		,	_lowercase  )
         UpperCamelCase_      =	min(_lowercase		,	_lowercase		,	self.cut_size  )
         UpperCamelCase_      =	[]
         for _ in range(_lowercase  ):
             UpperCamelCase_      =	int(torch.rand([]  ) ** self.cut_power * (max_size - min_size) + min_size  )
             UpperCamelCase_      =	torch.randint(0		,	sideX - size + 1		,	()  )
             UpperCamelCase_      =	torch.randint(0		,	sideY - size + 1		,	()  )
             UpperCamelCase_      =	pixel_values[:, :, offsety : offsety + size, offsetx : offsetx + size]
             cutouts.append(F.adaptive_avg_poolad(_lowercase		,	self.cut_size  )  )
         return torch.cat(_lowercase  )




def  lowerCAmelCase(			SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ )->	Optional[Any]:



    """simple docstring"""






    UpperCamelCase_      =	F.normalize(SCREAMING_SNAKE_CASE_ ,	dim=-1 )
    UpperCamelCase_      =	F.normalize(SCREAMING_SNAKE_CASE_ ,	dim=-1 )
    return (x - y).norm(dim=-1 ).div(2 ).arcsin().pow(2 ).mul(2 )




def  lowerCAmelCase(			SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_ )->	Tuple:



    """simple docstring"""






    for param in model.parameters():
        UpperCamelCase_      =	value






class 	__magic_name__				(       snake_case							):






     def __init__(							self		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	)->    List[Any]:
         super().__init__()
         self.register_modules(
             vae=_lowercase		,	text_encoder=_lowercase		,	clip_model=_lowercase		,	tokenizer=_lowercase		,	unet=_lowercase		,	scheduler=_lowercase		,	feature_extractor=_lowercase		,	)

         UpperCamelCase_      =	transforms.Normalize(mean=feature_extractor.image_mean		,	std=feature_extractor.image_std  )
         UpperCamelCase_      =	(
             feature_extractor.size
             if isinstance(feature_extractor.size		,	_lowercase  )
             else feature_extractor.size["shortest_edge"]
         )
         UpperCamelCase_      =	MakeCutouts(self.cut_out_size  )

         set_requires_grad(self.text_encoder		,	_lowercase  )
         set_requires_grad(self.clip_model		,	_lowercase  )






     def   UpperCAmelCase_							(							self		,	_lowercase = "auto"  )->    List[Any]:
         if slice_size == "auto":
             # half the attention head size is usually a good trade-off between
             # speed and memory
             UpperCamelCase_      =	self.unet.config.attention_head_dim // 2
         self.unet.set_attention_slice(_lowercase  )






     def   UpperCAmelCase_							(							self  )->    List[str]:
         self.enable_attention_slicing(_lowercase  )






     def   UpperCAmelCase_							(							self  )->    Optional[int]:
         set_requires_grad(self.vae		,	_lowercase  )






     def   UpperCAmelCase_							(							self  )->    List[str]:
         set_requires_grad(self.vae		,	_lowercase  )






     def   UpperCAmelCase_							(							self  )->    Union[str, Any]:
         set_requires_grad(self.unet		,	_lowercase  )






     def   UpperCAmelCase_							(							self  )->    Union[str, Any]:
         set_requires_grad(self.unet		,	_lowercase  )






     @torch.enable_grad()
     def   UpperCAmelCase_							(							self		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase=True		,	)->    Optional[int]:
         UpperCamelCase_      =	latents.detach().requires_grad_()

         UpperCamelCase_      =	self.scheduler.scale_model_input(_lowercase		,	_lowercase  )

         # predict the noise residual
         UpperCamelCase_      =	self.unet(_lowercase		,	_lowercase		,	encoder_hidden_states=_lowercase  ).sample

         if isinstance(self.scheduler		,	(PNDMScheduler, DDIMScheduler, DPMSolverMultistepScheduler)  ):
             UpperCamelCase_      =	self.scheduler.alphas_cumprod[timestep]
             UpperCamelCase_      =	1 - alpha_prod_t
             # compute predicted original sample from predicted noise also called
             # "predicted x_0" of formula (12) from https://arxiv.org/pdf/2010.02502.pdf
             UpperCamelCase_      =	(latents - beta_prod_t ** 0.5 * noise_pred) / alpha_prod_t ** 0.5

             UpperCamelCase_      =	torch.sqrt(_lowercase  )
             UpperCamelCase_      =	pred_original_sample * (fac) + latents * (1 - fac)
         elif isinstance(self.scheduler		,	_lowercase  ):
             UpperCamelCase_      =	self.scheduler.sigmas[index]
             UpperCamelCase_      =	latents - sigma * noise_pred
         else:
             raise ValueError(F"scheduler type {type(self.scheduler  )} not supported"  )

         UpperCamelCase_      =	1 / self.vae.config.scaling_factor * sample
         UpperCamelCase_      =	self.vae.decode(_lowercase  ).sample
         UpperCamelCase_      =	(image / 2 + 0.5).clamp(0		,	1  )

         if use_cutouts:
             UpperCamelCase_      =	self.make_cutouts(_lowercase		,	_lowercase  )
         else:
             UpperCamelCase_      =	transforms.Resize(self.cut_out_size  )(_lowercase  )
         UpperCamelCase_      =	self.normalize(_lowercase  ).to(latents.dtype  )

         UpperCamelCase_      =	self.clip_model.get_image_features(_lowercase  )
         UpperCamelCase_      =	image_embeddings_clip / image_embeddings_clip.norm(p=2		,	dim=-1		,	keepdim=_lowercase  )

         if use_cutouts:
             UpperCamelCase_      =	spherical_dist_loss(_lowercase		,	_lowercase  )
             UpperCamelCase_      =	dists.view([num_cutouts, sample.shape[0], -1]  )
             UpperCamelCase_      =	dists.sum(2  ).mean(0  ).sum() * clip_guidance_scale
         else:
             UpperCamelCase_      =	spherical_dist_loss(_lowercase		,	_lowercase  ).mean() * clip_guidance_scale

         UpperCamelCase_      =	-torch.autograd.grad(_lowercase		,	_lowercase  )[0]

         if isinstance(self.scheduler		,	_lowercase  ):
             UpperCamelCase_      =	latents.detach() + grads * (sigma**2)
             UpperCamelCase_      =	noise_pred_original
         else:
             UpperCamelCase_      =	noise_pred_original - torch.sqrt(_lowercase  ) * grads
         return noise_pred, latents






     @torch.no_grad()
     def __call__(							self		,	_lowercase		,	_lowercase = 512		,	_lowercase = 512		,	_lowercase = 50		,	_lowercase = 7.5		,	_lowercase = 1		,	_lowercase = 0.0		,	_lowercase = 100		,	_lowercase = None		,	_lowercase = 4		,	_lowercase = True		,	_lowercase = None		,	_lowercase = None		,	_lowercase = "pil"		,	_lowercase = True		,	)->    str:
         if isinstance(_lowercase		,	_lowercase  ):
             UpperCamelCase_      =	1
         elif isinstance(_lowercase		,	_lowercase  ):
             UpperCamelCase_      =	len(_lowercase  )
         else:
             raise ValueError(F"`prompt` has to be of type `str` or `list` but is {type(_lowercase  )}"  )

         if height % 8 != 0 or width % 8 != 0:
             raise ValueError(F"`height` and `width` have to be divisible by 8 but are {height} and {width}."  )

         # get prompt text embeddings
         UpperCamelCase_      =	self.tokenizer(
             _lowercase		,	padding="max_length"		,	max_length=self.tokenizer.model_max_length		,	truncation=_lowercase		,	return_tensors="pt"		,	)
         UpperCamelCase_      =	self.text_encoder(text_input.input_ids.to(self.device  )  )[0]
         # duplicate text embeddings for each generation per prompt
         UpperCamelCase_      =	text_embeddings.repeat_interleave(_lowercase		,	dim=0  )

         if clip_guidance_scale > 0:
             if clip_prompt is not None:
                 UpperCamelCase_      =	self.tokenizer(
                     _lowercase		,	padding="max_length"		,	max_length=self.tokenizer.model_max_length		,	truncation=_lowercase		,	return_tensors="pt"		,	).input_ids.to(self.device  )
             else:
                 UpperCamelCase_      =	text_input.input_ids.to(self.device  )
             UpperCamelCase_      =	self.clip_model.get_text_features(_lowercase  )
             UpperCamelCase_      =	text_embeddings_clip / text_embeddings_clip.norm(p=2		,	dim=-1		,	keepdim=_lowercase  )
             # duplicate text embeddings clip for each generation per prompt
             UpperCamelCase_      =	text_embeddings_clip.repeat_interleave(_lowercase		,	dim=0  )

         # here `guidance_scale` is defined analog to the guidance weight `w` of equation (2)
         # of the Imagen paper: https://arxiv.org/pdf/2205.11487.pdf . `guidance_scale = 1`
         # corresponds to doing no classifier free guidance.
         UpperCamelCase_      =	guidance_scale > 1.0
         # get unconditional embeddings for classifier free guidance
         if do_classifier_free_guidance:
             UpperCamelCase_      =	text_input.input_ids.shape[-1]
             UpperCamelCase_      =	self.tokenizer([""]		,	padding="max_length"		,	max_length=_lowercase		,	return_tensors="pt"  )
             UpperCamelCase_      =	self.text_encoder(uncond_input.input_ids.to(self.device  )  )[0]
             # duplicate unconditional embeddings for each generation per prompt
             UpperCamelCase_      =	uncond_embeddings.repeat_interleave(_lowercase		,	dim=0  )

             # For classifier free guidance, we need to do two forward passes.
             # Here we concatenate the unconditional and text embeddings into a single batch
             # to avoid doing two forward passes
             UpperCamelCase_      =	torch.cat([uncond_embeddings, text_embeddings]  )

         # get the initial random noise unless the user supplied it

         # Unlike in other pipelines, latents need to be generated in the target device
         # for 1-to-1 results reproducibility with the CompVis implementation.
         # However this currently doesn't work in `mps`.
         UpperCamelCase_      =	(batch_size * num_images_per_prompt, self.unet.config.in_channels, height // 8, width // 8)
         UpperCamelCase_      =	text_embeddings.dtype
         if latents is None:
             if self.device.type == "mps":
                 # randn does not work reproducibly on mps
                 UpperCamelCase_      =	torch.randn(_lowercase		,	generator=_lowercase		,	device="cpu"		,	dtype=_lowercase  ).to(
                     self.device  )
             else:
                 UpperCamelCase_      =	torch.randn(_lowercase		,	generator=_lowercase		,	device=self.device		,	dtype=_lowercase  )
         else:
             if latents.shape != latents_shape:
                 raise ValueError(F"Unexpected latents shape, got {latents.shape}, expected {latents_shape}"  )
             UpperCamelCase_      =	latents.to(self.device  )

         # set timesteps
         UpperCamelCase_      =	"offset" in set(inspect.signature(self.scheduler.set_timesteps  ).parameters.keys()  )
         UpperCamelCase_      =	{}
         if accepts_offset:
             UpperCamelCase_      =	1

         self.scheduler.set_timesteps(_lowercase		,	**_lowercase  )

         # Some schedulers like PNDM have timesteps as arrays
         # It's more optimized to move all timesteps to correct device beforehand
         UpperCamelCase_      =	self.scheduler.timesteps.to(self.device  )

         # scale the initial noise by the standard deviation required by the scheduler
         UpperCamelCase_      =	latents * self.scheduler.init_noise_sigma

         # prepare extra kwargs for the scheduler step, since not all schedulers have the same signature
         # eta (η) is only used with the DDIMScheduler, it will be ignored for other schedulers.
         # eta corresponds to η in DDIM paper: https://arxiv.org/abs/2010.02502
         # and should be between [0, 1]
         UpperCamelCase_      =	"eta" in set(inspect.signature(self.scheduler.step  ).parameters.keys()  )
         UpperCamelCase_      =	{}
         if accepts_eta:
             UpperCamelCase_      =	eta

         # check if the scheduler accepts generator
         UpperCamelCase_      =	"generator" in set(inspect.signature(self.scheduler.step  ).parameters.keys()  )
         if accepts_generator:
             UpperCamelCase_      =	generator

         for i, t in enumerate(self.progress_bar(_lowercase  )  ):
             # expand the latents if we are doing classifier free guidance
             UpperCamelCase_      =	torch.cat([latents] * 2  ) if do_classifier_free_guidance else latents
             UpperCamelCase_      =	self.scheduler.scale_model_input(_lowercase		,	_lowercase  )

             # predict the noise residual
             UpperCamelCase_      =	self.unet(_lowercase		,	_lowercase		,	encoder_hidden_states=_lowercase  ).sample

             # perform classifier free guidance
             if do_classifier_free_guidance:
                 UpperCamelCase_     ,					UpperCamelCase_      =	noise_pred.chunk(2  )
                 UpperCamelCase_      =	noise_pred_uncond + guidance_scale * (noise_pred_text - noise_pred_uncond)

             # perform clip guidance
             if clip_guidance_scale > 0:
                 UpperCamelCase_      =	(
                     text_embeddings.chunk(2  )[1] if do_classifier_free_guidance else text_embeddings
                 )
                 UpperCamelCase_     ,					UpperCamelCase_      =	self.cond_fn(
                     _lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	_lowercase		,	)

             # compute the previous noisy sample x_t -> x_t-1
             UpperCamelCase_      =	self.scheduler.step(_lowercase		,	_lowercase		,	_lowercase		,	**_lowercase  ).prev_sample

         # scale and decode the image latents with vae
         UpperCamelCase_      =	1 / self.vae.config.scaling_factor * latents
         UpperCamelCase_      =	self.vae.decode(_lowercase  ).sample

         UpperCamelCase_      =	(image / 2 + 0.5).clamp(0		,	1  )
         UpperCamelCase_      =	image.cpu().permute(0		,	2		,	3		,	1  ).numpy()

         if output_type == "pil":
             UpperCamelCase_      =	self.numpy_to_pil(_lowercase  )

         if not return_dict:
             return (image, None)

         return StableDiffusionPipelineOutput(images=_lowercase		,	nsfw_content_detected=_lowercase  )



from __future__ import annotations




def  lowerCAmelCase(			SCREAMING_SNAKE_CASE_ )->	str:



    """simple docstring"""






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




def  lowerCAmelCase(			SCREAMING_SNAKE_CASE_ )->	Dict:



    """simple docstring"""






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




def  lowerCAmelCase(			)->	Dict:



    """simple docstring"""






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

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

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