
'''simple docstring'''





import argparse
import csv
import json
import math
import time

import numpy as np
import torch
import torch.optim as optim
import torch.utils.data as data
from nltk.tokenize.treebank import TreebankWordDetokenizer
from pplm_classification_head import ClassificationHead
from torch import nn
from torchtext import data as torchtext_data
from torchtext import datasets
from tqdm import tqdm, trange

from transformers import GPTaLMHeadModel, GPTaTokenizer


torch.manual_seed(0)
np.random.seed(0)
a__						:				Optional[int]           =    1E-10
a__						:				str           =    "This is incredible! I love it, this is the best chicken I have ever had."
a__						:				List[Any]           =    1_0_0


class 	UpperCamelCase__					(      nn.Module):






	def __init__(     self					:List[Any]		,			_A					:List[str]		,			_A					:Optional[int]="gpt2-medium"		,			_A					:Tuple=False		,			_A					:List[str]="cpu"     )			->     int:







							'''simple docstring'''



							super().__init__()
							__A    		=     GPTaTokenizer.from_pretrained(_A     )
							__A    		=     GPTaLMHeadModel.from_pretrained(_A     )
							__A    		=     self.encoder.transformer.config.hidden_size
							__A    		=     ClassificationHead(class_size=_A		,			embed_size=self.embed_size     )
							__A    		=     cached_mode
							__A    		=     device






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







							'''simple docstring'''



							return self.classifier_head






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







							'''simple docstring'''



							for param in self.encoder.parameters():
													__A    		=     False
							self.classifier_head.train()






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







							'''simple docstring'''



							__A    		=     x.ne(0     ).unsqueeze(2     ).repeat(1		,			1		,			self.embed_size     ).float().to(self.device     ).detach()
							__A    		=     self.encoder.transformer(_A     )['last_hidden_state']
							__A    		=     hidden * mask
							__A    		=     torch.sum(_A		,			dim=1     ) / (torch.sum(_A		,			dim=1     ).detach() + EPSILON)
							return avg_hidden






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







							'''simple docstring'''



							if self.cached_mode:
													__A    		=     x.to(self.device     )
							else:
													__A    		=     self.avg_representation(x.to(self.device     )     )

							__A    		=     self.classifier_head(_A     )
							__A    		=     nn.functional.log_softmax(_A		,			dim=-1     )

							return probs


class 	UpperCamelCase__					(      data.Dataset):






	def __init__(     self					:Optional[Any]		,			_A					:str		,			_A					:Dict     )			->     Optional[int]:







							'''simple docstring'''



							__A    		=     X
							__A    		=     y






	def __len__(     self					:int     )			->     int:







							'''simple docstring'''



							return len(self.X     )






	def __getitem__(     self					:Union[str, Any]		,			_A					:str     )			->     List[str]:







							'''simple docstring'''



							__A    		=     {}
							__A    		=     self.X[index]
							__A    		=     self.y[index]
							return data





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







						"""simple docstring"""
						def pad_sequences(UpperCAmelCase		):
												__A    		=     [len(UpperCAmelCase		) for seq in sequences]

												__A    		=     torch.zeros(len(UpperCAmelCase		) ,					max(UpperCAmelCase		)		).long()  # padding value = 0

												for i, seq in enumerate(UpperCAmelCase		):
																		__A    		=     lengths[i]
																		__A    		=     seq[:end]

												return padded_sequences, lengths

						__A    		=     {}
						for key in data[0].keys():
												__A    		=     [d[key] for d in data]

						__A		, __A    		=     pad_sequences(item_info['X']		)
						__A    		=     torch.tensor(item_info['y'] ,					dtype=torch.long		)

						return x_batch, y_batch





def     snake_case							(						UpperCAmelCase		)->     Dict:







						"""simple docstring"""
						__A    		=     {}
						for key in data[0].keys():
												__A    		=     [d[key] for d in data]

						__A    		=     torch.cat(item_info['X'] ,					0		)
						__A    		=     torch.tensor(item_info['y'] ,					dtype=torch.long		)

						return x_batch, y_batch





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase=0 ,					UpperCAmelCase=1_0 ,					UpperCAmelCase="cpu"		)->     Optional[Any]:







						"""simple docstring"""
						__A    		=     0
						discriminator.train_custom()
						for batch_idx, (input_t, target_t) in enumerate(UpperCAmelCase		):
												__A		, __A    		=     input_t.to(UpperCAmelCase		), target_t.to(UpperCAmelCase		)

												optimizer.zero_grad()

												__A    		=     discriminator(UpperCAmelCase		)
												__A    		=     nn.functional.nll_loss(UpperCAmelCase ,					UpperCAmelCase		)
												loss.backward(retain_graph=UpperCAmelCase		)
												optimizer.step()

												samples_so_far += len(UpperCAmelCase		)

												if batch_idx % log_interval == 0:
																		print(
																		    'Train Epoch: {} [{}/{} ({:.0f}%)]\tLoss: {:.6f}'.format(
																		        epoch + 1 ,					UpperCAmelCase ,					len(data_loader.dataset		) ,					1_0_0 * samples_so_far / len(data_loader.dataset		) ,					loss.item() ,					)		)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase="cpu"		)->     Tuple:







						"""simple docstring"""
						discriminator.eval()
						__A    		=     0
						__A    		=     0
						with torch.no_grad():
												for input_t, target_t in data_loader:
																		__A		, __A    		=     input_t.to(UpperCAmelCase		), target_t.to(UpperCAmelCase		)
																		__A    		=     discriminator(UpperCAmelCase		)
																		# sum up batch loss
																		test_loss += nn.functional.nll_loss(UpperCAmelCase ,					UpperCAmelCase ,					reduction='sum'		).item()
																		# get the index of the max log-probability
																		__A    		=     output_t.argmax(dim=1 ,					keepdim=UpperCAmelCase		)
																		correct += pred_t.eq(target_t.view_as(UpperCAmelCase		)		).sum().item()

						test_loss /= len(data_loader.dataset		)

						print(
						    'Performance on test set: Average loss: {:.4f}, Accuracy: {}/{} ({:.0f}%)'.format(
						        UpperCAmelCase ,					UpperCAmelCase ,					len(data_loader.dataset		) ,					100.0 * correct / len(data_loader.dataset		)		)		)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase=False ,					UpperCAmelCase="cpu"		)->     Tuple:







						"""simple docstring"""
						__A    		=     model.tokenizer.encode(UpperCAmelCase		)
						__A    		=     torch.tensor([input_t] ,					dtype=torch.long ,					device=UpperCAmelCase		)
						if cached:
												__A    		=     model.avg_representation(UpperCAmelCase		)

						__A    		=     model(UpperCAmelCase		).data.cpu().numpy().flatten().tolist()
						print('Input sentence:' ,					UpperCAmelCase		)
						print(
						    'Predictions:' ,					', '.join('{}: {:.4f}'.format(UpperCAmelCase ,					math.exp(UpperCAmelCase		)		) for c, log_prob in zip(UpperCAmelCase ,					UpperCAmelCase		)		) ,					)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase=False ,					UpperCAmelCase="cpu"		)->     Dict:







						"""simple docstring"""
						__A    		=     torch.utils.data.DataLoader(dataset=UpperCAmelCase ,					batch_size=UpperCAmelCase ,					collate_fn=UpperCAmelCase		)

						__A    		=     []
						__A    		=     []
						for batch_idx, (x, y) in enumerate(tqdm(UpperCAmelCase ,					ascii=UpperCAmelCase		)		):
												with torch.no_grad():
																		__A    		=     x.to(UpperCAmelCase		)
																		__A    		=     discriminator.avg_representation(UpperCAmelCase		).cpu().detach()
																		__A    		=     torch.unbind(avg_rep.unsqueeze(1		)		)
																		xs += avg_rep_list
																		ys += y.cpu().numpy().tolist()

						__A    		=     torch.utils.data.DataLoader(
						    dataset=Dataset(UpperCAmelCase ,					UpperCAmelCase		) ,					batch_size=UpperCAmelCase ,					shuffle=UpperCAmelCase ,					collate_fn=UpperCAmelCase		)

						return data_loader





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase=None ,					UpperCAmelCase="gpt2-medium" ,					UpperCAmelCase=1_0 ,					UpperCAmelCase=6_4 ,					UpperCAmelCase=1_0 ,					UpperCAmelCase=False ,					UpperCAmelCase=False ,					UpperCAmelCase=False ,					)->     Optional[int]:







						"""simple docstring"""
						__A    		=     'cuda' if torch.cuda.is_available() and not no_cuda else 'cpu'

						print('Preprocessing {} dataset...'.format(UpperCAmelCase		)		)
						__A    		=     time.time()

						if dataset == "SST":
												__A    		=     ['positive', 'negative', 'very positive', 'very negative', 'neutral']
												__A    		=     {c: i for i, c in enumerate(UpperCAmelCase		)}

												__A    		=     Discriminator(
												    class_size=len(UpperCAmelCase		) ,					pretrained_model=UpperCAmelCase ,					cached_mode=UpperCAmelCase ,					device=UpperCAmelCase		).to(UpperCAmelCase		)

												__A    		=     torchtext_data.Field()
												__A    		=     torchtext_data.Field(sequential=UpperCAmelCase		)
												__A		, __A		, __A    		=     datasets.SST.splits(
												    UpperCAmelCase ,					UpperCAmelCase ,					fine_grained=UpperCAmelCase ,					train_subtrees=UpperCAmelCase ,					)

												__A    		=     []
												__A    		=     []
												for i in trange(len(UpperCAmelCase		) ,					ascii=UpperCAmelCase		):
																		__A    		=     TreebankWordDetokenizer().detokenize(vars(train_data[i]		)['text']		)
																		__A    		=     discriminator.tokenizer.encode(UpperCAmelCase		)
																		__A    		=     torch.tensor([5_0_2_5_6] + seq ,					device=UpperCAmelCase ,					dtype=torch.long		)
																		x.append(UpperCAmelCase		)
																		y.append(classaidx[vars(train_data[i]		)['label']]		)
												__A    		=     Dataset(UpperCAmelCase ,					UpperCAmelCase		)

												__A    		=     []
												__A    		=     []
												for i in trange(len(UpperCAmelCase		) ,					ascii=UpperCAmelCase		):
																		__A    		=     TreebankWordDetokenizer().detokenize(vars(test_data[i]		)['text']		)
																		__A    		=     discriminator.tokenizer.encode(UpperCAmelCase		)
																		__A    		=     torch.tensor([5_0_2_5_6] + seq ,					device=UpperCAmelCase ,					dtype=torch.long		)
																		test_x.append(UpperCAmelCase		)
																		test_y.append(classaidx[vars(test_data[i]		)['label']]		)
												__A    		=     Dataset(UpperCAmelCase ,					UpperCAmelCase		)

												__A    		=     {
												    'class_size': len(UpperCAmelCase		),
												    'embed_size': discriminator.embed_size,
												    'pretrained_model': pretrained_model,
												    'class_vocab': classaidx,
												    'default_class': 2,
												}

						elif dataset == "clickbait":
												__A    		=     ['non_clickbait', 'clickbait']
												__A    		=     {c: i for i, c in enumerate(UpperCAmelCase		)}

												__A    		=     Discriminator(
												    class_size=len(UpperCAmelCase		) ,					pretrained_model=UpperCAmelCase ,					cached_mode=UpperCAmelCase ,					device=UpperCAmelCase		).to(UpperCAmelCase		)

												with open('datasets/clickbait/clickbait_train_prefix.txt'		) as f:
																		__A    		=     []
																		for i, line in enumerate(UpperCAmelCase		):
																								try:
																														data.append(eval(UpperCAmelCase		)		)
																								except Exception:
																														print('Error evaluating line {}: {}'.format(UpperCAmelCase ,					UpperCAmelCase		)		)
																														continue
												__A    		=     []
												__A    		=     []
												with open('datasets/clickbait/clickbait_train_prefix.txt'		) as f:
																		for i, line in enumerate(tqdm(UpperCAmelCase ,					ascii=UpperCAmelCase		)		):
																								try:
																														__A    		=     eval(UpperCAmelCase		)
																														__A    		=     discriminator.tokenizer.encode(d['text']		)

																														if len(UpperCAmelCase		) < max_length_seq:
																																				__A    		=     torch.tensor([5_0_2_5_6] + seq ,					device=UpperCAmelCase ,					dtype=torch.long		)
																														else:
																																				print('Line {} is longer than maximum length {}'.format(UpperCAmelCase ,					UpperCAmelCase		)		)
																																				continue
																														x.append(UpperCAmelCase		)
																														y.append(d['label']		)
																								except Exception:
																														print('Error evaluating / tokenizing line {}, skipping it'.format(UpperCAmelCase		)		)
																														pass

												__A    		=     Dataset(UpperCAmelCase ,					UpperCAmelCase		)
												__A    		=     int(0.9 * len(UpperCAmelCase		)		)
												__A    		=     len(UpperCAmelCase		) - train_size
												__A		, __A    		=     torch.utils.data.random_split(UpperCAmelCase ,					[train_size, test_size]		)

												__A    		=     {
												    'class_size': len(UpperCAmelCase		),
												    'embed_size': discriminator.embed_size,
												    'pretrained_model': pretrained_model,
												    'class_vocab': classaidx,
												    'default_class': 1,
												}

						elif dataset == "toxic":
												__A    		=     ['non_toxic', 'toxic']
												__A    		=     {c: i for i, c in enumerate(UpperCAmelCase		)}

												__A    		=     Discriminator(
												    class_size=len(UpperCAmelCase		) ,					pretrained_model=UpperCAmelCase ,					cached_mode=UpperCAmelCase ,					device=UpperCAmelCase		).to(UpperCAmelCase		)

												__A    		=     []
												__A    		=     []
												with open('datasets/toxic/toxic_train.txt'		) as f:
																		for i, line in enumerate(tqdm(UpperCAmelCase ,					ascii=UpperCAmelCase		)		):
																								try:
																														__A    		=     eval(UpperCAmelCase		)
																														__A    		=     discriminator.tokenizer.encode(d['text']		)

																														if len(UpperCAmelCase		) < max_length_seq:
																																				__A    		=     torch.tensor([5_0_2_5_6] + seq ,					device=UpperCAmelCase ,					dtype=torch.long		)
																														else:
																																				print('Line {} is longer than maximum length {}'.format(UpperCAmelCase ,					UpperCAmelCase		)		)
																																				continue
																														x.append(UpperCAmelCase		)
																														y.append(int(np.sum(d['label']		) > 0		)		)
																								except Exception:
																														print('Error evaluating / tokenizing line {}, skipping it'.format(UpperCAmelCase		)		)
																														pass

												__A    		=     Dataset(UpperCAmelCase ,					UpperCAmelCase		)
												__A    		=     int(0.9 * len(UpperCAmelCase		)		)
												__A    		=     len(UpperCAmelCase		) - train_size
												__A		, __A    		=     torch.utils.data.random_split(UpperCAmelCase ,					[train_size, test_size]		)

												__A    		=     {
												    'class_size': len(UpperCAmelCase		),
												    'embed_size': discriminator.embed_size,
												    'pretrained_model': pretrained_model,
												    'class_vocab': classaidx,
												    'default_class': 0,
												}

						else:  # if dataset == "generic":
												# This assumes the input dataset is a TSV with the following structure:
												# class \t text

												if dataset_fp is None:
																		raise ValueError('When generic dataset is selected, dataset_fp needs to be specified aswell.'		)

												__A    		=     set()
												with open(UpperCAmelCase		) as f:
																		__A    		=     csv.reader(UpperCAmelCase ,					delimiter='\t'		)
																		for row in tqdm(UpperCAmelCase ,					ascii=UpperCAmelCase		):
																								if row:
																														classes.add(row[0]		)

												__A    		=     sorted(UpperCAmelCase		)
												__A    		=     {c: i for i, c in enumerate(UpperCAmelCase		)}

												__A    		=     Discriminator(
												    class_size=len(UpperCAmelCase		) ,					pretrained_model=UpperCAmelCase ,					cached_mode=UpperCAmelCase ,					device=UpperCAmelCase		).to(UpperCAmelCase		)

												__A    		=     []
												__A    		=     []
												with open(UpperCAmelCase		) as f:
																		__A    		=     csv.reader(UpperCAmelCase ,					delimiter='\t'		)
																		for i, row in enumerate(tqdm(UpperCAmelCase ,					ascii=UpperCAmelCase		)		):
																								if row:
																														__A    		=     row[0]
																														__A    		=     row[1]

																														try:
																																				__A    		=     discriminator.tokenizer.encode(UpperCAmelCase		)
																																				if len(UpperCAmelCase		) < max_length_seq:
																																										__A    		=     torch.tensor([5_0_2_5_6] + seq ,					device=UpperCAmelCase ,					dtype=torch.long		)

																																				else:
																																										print('Line {} is longer than maximum length {}'.format(UpperCAmelCase ,					UpperCAmelCase		)		)
																																										continue

																																				x.append(UpperCAmelCase		)
																																				y.append(classaidx[label]		)

																														except Exception:
																																				print('Error tokenizing line {}, skipping it'.format(UpperCAmelCase		)		)
																																				pass

												__A    		=     Dataset(UpperCAmelCase ,					UpperCAmelCase		)
												__A    		=     int(0.9 * len(UpperCAmelCase		)		)
												__A    		=     len(UpperCAmelCase		) - train_size
												__A		, __A    		=     torch.utils.data.random_split(UpperCAmelCase ,					[train_size, test_size]		)

												__A    		=     {
												    'class_size': len(UpperCAmelCase		),
												    'embed_size': discriminator.embed_size,
												    'pretrained_model': pretrained_model,
												    'class_vocab': classaidx,
												    'default_class': 0,
												}

						__A    		=     time.time()
						print('Preprocessed {} data points'.format(len(UpperCAmelCase		) + len(UpperCAmelCase		)		)		)
						print('Data preprocessing took: {:.3f}s'.format(end - start		)		)

						if cached:
												print('Building representation cache...'		)

												__A    		=     time.time()

												__A    		=     get_cached_data_loader(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					shuffle=UpperCAmelCase ,					device=UpperCAmelCase		)

												__A    		=     get_cached_data_loader(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					device=UpperCAmelCase		)

												__A    		=     time.time()
												print('Building representation cache took: {:.3f}s'.format(end - start		)		)

						else:
												__A    		=     torch.utils.data.DataLoader(
												    dataset=UpperCAmelCase ,					batch_size=UpperCAmelCase ,					shuffle=UpperCAmelCase ,					collate_fn=UpperCAmelCase		)
												__A    		=     torch.utils.data.DataLoader(dataset=UpperCAmelCase ,					batch_size=UpperCAmelCase ,					collate_fn=UpperCAmelCase		)

						if save_model:
												with open('{}_classifier_head_meta.json'.format(UpperCAmelCase		) ,					'w'		) as meta_file:
																		json.dump(UpperCAmelCase ,					UpperCAmelCase		)

						__A    		=     optim.Adam(discriminator.parameters() ,					lr=0.0001		)

						for epoch in range(UpperCAmelCase		):
												__A    		=     time.time()
												print('\nEpoch' ,					epoch + 1		)

												train_epoch(
												    discriminator=UpperCAmelCase ,					data_loader=UpperCAmelCase ,					optimizer=UpperCAmelCase ,					epoch=UpperCAmelCase ,					log_interval=UpperCAmelCase ,					device=UpperCAmelCase ,					)
												evaluate_performance(data_loader=UpperCAmelCase ,					discriminator=UpperCAmelCase ,					device=UpperCAmelCase		)

												__A    		=     time.time()
												print('Epoch took: {:.3f}s'.format(end - start		)		)

												print('\nExample prediction'		)
												predict(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					cached=UpperCAmelCase ,					device=UpperCAmelCase		)

												if save_model:
																		# torch.save(discriminator.state_dict(),
																		#           "{}_discriminator_{}.pt".format(
																		#               args.dataset, epoch + 1
																		#               ))
																		torch.save(
																		    discriminator.get_classifier().state_dict() ,					'{}_classifier_head_epoch_{}.pt'.format(UpperCAmelCase ,					epoch + 1		) ,					)


if __name__ == "__main__":
	a__						:				Union[str, Any]           =    argparse.ArgumentParser(description="Train a discriminator on top of GPT-2 representations")
	parser.add_argument(
	    "--dataset",
	    type=str,
	    default="SST",
	    choices=("SST", "clickbait", "toxic", "generic"),
	    help=(
	        "dataset to train the discriminator on."
	        "In case of generic, the dataset is expected"
	        "to be a TSBV file with structure: class \\t text"
	    ),
	)
	parser.add_argument(
	    "--dataset_fp",
	    type=str,
	    default="",
	    help="File path of the dataset to use. Needed only in case of generic datadset",
	)
	parser.add_argument(
	    "--pretrained_model", type=str, default="gpt2-medium", help="Pretrained model to use as encoder"
	)
	parser.add_argument("--epochs", type=int, default=1_0, metavar="N", help="Number of training epochs")
	parser.add_argument(
	    "--batch_size", type=int, default=6_4, metavar="N", help="input batch size for training (default: 64)"
	)
	parser.add_argument(
	    "--log_interval",
	    type=int,
	    default=1_0,
	    metavar="N",
	    help="how many batches to wait before logging training status",
	)
	parser.add_argument("--save_model", action="store_true", help="whether to save the model")
	parser.add_argument("--cached", action="store_true", help="whether to cache the input representations")
	parser.add_argument("--no_cuda", action="store_true", help="use to turn off cuda")
	a__						:				List[Any]           =    parser.parse_args()

	train_discriminator(**(vars(args)))








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






