



from collections import deque
from math import floor
from random import random
from time import time



class        lowerCAmelCase__					:


				def __init__(							self      :  List[str]       )		->     List[str]:
											A      						=    {}


				def __UpperCamelCase						(							self      :  Dict						, __UpperCamelCase      :  List[str]						, __UpperCamelCase      :  int						, __UpperCamelCase      :  Any=1       )		->     Dict:
											if self.graph.get(__UpperCamelCase       ):
																		if self.graph[u].count([w, v]       ) == 0:
																									self.graph[u].append([w, v]       )
											else:
																		A      						=    [[w, v]]
											if not self.graph.get(__UpperCamelCase       ):
																		A      						=    []


				def __UpperCamelCase						(							self      :  int       )		->     Any:
											return list(self.graph       )


				def __UpperCamelCase						(							self      :  str						, __UpperCamelCase      :  Dict						, __UpperCamelCase      :  Optional[int]       )		->     Dict:
											if self.graph.get(__UpperCamelCase       ):
																		for _ in self.graph[u]:
																									if _[1] == v:
																																self.graph[u].remove(__UpperCamelCase       )


				def __UpperCamelCase						(							self      :  Optional[int]						, __UpperCamelCase      :  Dict=-2						, __UpperCamelCase      :  str=-1       )		->     int:
											if s == d:
																		return []
											A      						=    []
											A      						=    []
											if s == -2:
																		A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    s

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if visited.count(node[1]       ) < 1:
																																							if node[1] == d:
																																														visited.append(__UpperCamelCase       )
																																														return visited
																																							else:
																																														stack.append(node[1]       )
																																														visited.append(node[1]       )
																																														A      						=    node[1]
																																														break

            # check if all the children are visited
																		if s == ss:
																									stack.pop()
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return visited


				def __UpperCamelCase						(							self      :  List[Any]						, __UpperCamelCase      :  List[Any]=-1       )		->     List[Any]:
											if c == -1:
																		A      						=    floor(random() * 10_000       ) + 10
											for i in range(__UpperCamelCase       ):
																		# every vertex has max 100 edges
																		for _ in range(floor(random() * 102       ) + 1       ):
																									A      						=    floor(random() * c       ) + 1
																									if n != i:
																																self.add_pair(__UpperCamelCase						, __UpperCamelCase						, 1       )


				def __UpperCamelCase						(							self      :  Optional[int]						, __UpperCamelCase      :  Dict=-2       )		->     Any:
											A      						=    deque()
											A      						=    []
											if s == -2:
																		A      						=    list(self.graph       )[0]
											d.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											while d:
																		A      						=    d.popleft()
																		if len(self.graph[s]       ) != 0:
																									for node in self.graph[s]:
																																if visited.count(node[1]       ) < 1:
																																							d.append(node[1]       )
																																							visited.append(node[1]       )
											return visited


				def __UpperCamelCase						(							self      :  Tuple						, __UpperCamelCase      :  int       )		->     str:
											A      						=    0
											for x in self.graph:
																		for y in self.graph[x]:
																									if y[1] == u:
																																count += 1
											return count


				def __UpperCamelCase						(							self      :  Optional[Any]						, __UpperCamelCase      :  List[Any]       )		->     Optional[Any]:
											return len(self.graph[u]       )


				def __UpperCamelCase						(							self      :  Any						, __UpperCamelCase      :  Optional[int]=-2       )		->     List[str]:
											A      						=    []
											A      						=    []
											if s == -2:
																		A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    s
											A      						=    []

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if visited.count(node[1]       ) < 1:
																																							stack.append(node[1]       )
																																							visited.append(node[1]       )
																																							A      						=    node[1]
																																							break

            # check if all the children are visited
																		if s == ss:
																									sorted_nodes.append(stack.pop()       )
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return sorted_nodes


				def __UpperCamelCase						(							self      :  List[Any]       )		->     int:
											A      						=    []
											A      						=    []
											A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    -2
											A      						=    []
											A      						=    s
											A      						=    False
											A      						=    set()

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if (
																																    visited.count(node[1]       ) > 0
																																    and node[1] != parent
																																    and indirect_parents.count(node[1]       ) > 0
																																    and not on_the_way_back
																																):
																																							A      						=    len(__UpperCamelCase       ) - 1
																																							while len_stack >= 0:
																																														if stack[len_stack] == node[1]:
																																																					anticipating_nodes.add(node[1]       )
																																																					break
																																														else:
																																																					anticipating_nodes.add(stack[len_stack]       )
																																																					len_stack -= 1
																																if visited.count(node[1]       ) < 1:
																																							stack.append(node[1]       )
																																							visited.append(node[1]       )
																																							A      						=    node[1]
																																							break

            # check if all the children are visited
																		if s == ss:
																									stack.pop()
																									A      						=    True
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    False
																									indirect_parents.append(__UpperCamelCase       )
																									A      						=    s
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return list(__UpperCamelCase       )


				def __UpperCamelCase						(							self      :  str       )		->     Optional[int]:
											A      						=    []
											A      						=    []
											A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    -2
											A      						=    []
											A      						=    s
											A      						=    False
											A      						=    set()

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if (
																																    visited.count(node[1]       ) > 0
																																    and node[1] != parent
																																    and indirect_parents.count(node[1]       ) > 0
																																    and not on_the_way_back
																																):
																																							A      						=    len(__UpperCamelCase       ) - 1
																																							while len_stack_minus_one >= 0:
																																														if stack[len_stack_minus_one] == node[1]:
																																																					anticipating_nodes.add(node[1]       )
																																																					break
																																														else:
																																																					return True
																																if visited.count(node[1]       ) < 1:
																																							stack.append(node[1]       )
																																							visited.append(node[1]       )
																																							A      						=    node[1]
																																							break

            # check if all the children are visited
																		if s == ss:
																									stack.pop()
																									A      						=    True
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    False
																									indirect_parents.append(__UpperCamelCase       )
																									A      						=    s
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return False


				def __UpperCamelCase						(							self      :  Tuple						, __UpperCamelCase      :  Tuple=-2						, __UpperCamelCase      :  Union[str, Any]=-1       )		->     Dict:
											A      						=    time()
											self.dfs(__UpperCamelCase						, __UpperCamelCase       )
											A      						=    time()
											return end - begin


				def __UpperCamelCase						(							self      :  Any						, __UpperCamelCase      :  List[str]=-2       )		->     Optional[int]:
											A      						=    time()
											self.bfs(__UpperCamelCase       )
											A      						=    time()
											return end - begin





class        lowerCAmelCase__					:


				def __init__(							self      :  int       )		->     Optional[int]:
											A      						=    {}


				def __UpperCamelCase						(							self      :  Any						, __UpperCamelCase      :  Optional[int]						, __UpperCamelCase      :  Dict						, __UpperCamelCase      :  Union[str, Any]=1       )		->     Any:
											# check if the u exists
											if self.graph.get(__UpperCamelCase       ):
																		# if there already is a edge
																		if self.graph[u].count([w, v]       ) == 0:
																									self.graph[u].append([w, v]       )
											else:
																		# if u does not exist
																		A      						=    [[w, v]]
											# add the other way
											if self.graph.get(__UpperCamelCase       ):
																		# if there already is a edge
																		if self.graph[v].count([w, u]       ) == 0:
																									self.graph[v].append([w, u]       )
											else:
																		# if u does not exist
																		A      						=    [[w, u]]


				def __UpperCamelCase						(							self      :  int						, __UpperCamelCase      :  Optional[int]						, __UpperCamelCase      :  Dict       )		->     Dict:
											if self.graph.get(__UpperCamelCase       ):
																		for _ in self.graph[u]:
																									if _[1] == v:
																																self.graph[u].remove(__UpperCamelCase       )
        # the other way round
											if self.graph.get(__UpperCamelCase       ):
																		for _ in self.graph[v]:
																									if _[1] == u:
																																self.graph[v].remove(__UpperCamelCase       )


				def __UpperCamelCase						(							self      :  List[Any]						, __UpperCamelCase      :  Optional[Any]=-2						, __UpperCamelCase      :  List[str]=-1       )		->     Optional[int]:
											if s == d:
																		return []
											A      						=    []
											A      						=    []
											if s == -2:
																		A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    s

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if visited.count(node[1]       ) < 1:
																																							if node[1] == d:
																																														visited.append(__UpperCamelCase       )
																																														return visited
																																							else:
																																														stack.append(node[1]       )
																																														visited.append(node[1]       )
																																														A      						=    node[1]
																																														break

            # check if all the children are visited
																		if s == ss:
																									stack.pop()
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return visited


				def __UpperCamelCase						(							self      :  int						, __UpperCamelCase      :  str=-1       )		->     Optional[Any]:
											if c == -1:
																		A      						=    floor(random() * 10_000       ) + 10
											for i in range(__UpperCamelCase       ):
																		# every vertex has max 100 edges
																		for _ in range(floor(random() * 102       ) + 1       ):
																									A      						=    floor(random() * c       ) + 1
																									if n != i:
																																self.add_pair(__UpperCamelCase						, __UpperCamelCase						, 1       )


				def __UpperCamelCase						(							self      :  int						, __UpperCamelCase      :  List[Any]=-2       )		->     int:
											A      						=    deque()
											A      						=    []
											if s == -2:
																		A      						=    list(self.graph       )[0]
											d.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											while d:
																		A      						=    d.popleft()
																		if len(self.graph[s]       ) != 0:
																									for node in self.graph[s]:
																																if visited.count(node[1]       ) < 1:
																																							d.append(node[1]       )
																																							visited.append(node[1]       )
											return visited


				def __UpperCamelCase						(							self      :  Optional[int]						, __UpperCamelCase      :  str       )		->     Optional[Any]:
											return len(self.graph[u]       )


				def __UpperCamelCase						(							self      :  Optional[int]       )		->     str:
											A      						=    []
											A      						=    []
											A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    -2
											A      						=    []
											A      						=    s
											A      						=    False
											A      						=    set()

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if (
																																    visited.count(node[1]       ) > 0
																																    and node[1] != parent
																																    and indirect_parents.count(node[1]       ) > 0
																																    and not on_the_way_back
																																):
																																							A      						=    len(__UpperCamelCase       ) - 1
																																							while len_stack >= 0:
																																														if stack[len_stack] == node[1]:
																																																					anticipating_nodes.add(node[1]       )
																																																					break
																																														else:
																																																					anticipating_nodes.add(stack[len_stack]       )
																																																					len_stack -= 1
																																if visited.count(node[1]       ) < 1:
																																							stack.append(node[1]       )
																																							visited.append(node[1]       )
																																							A      						=    node[1]
																																							break

            # check if all the children are visited
																		if s == ss:
																									stack.pop()
																									A      						=    True
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    False
																									indirect_parents.append(__UpperCamelCase       )
																									A      						=    s
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return list(__UpperCamelCase       )


				def __UpperCamelCase						(							self      :  Optional[int]       )		->     Optional[int]:
											A      						=    []
											A      						=    []
											A      						=    list(self.graph       )[0]
											stack.append(__UpperCamelCase       )
											visited.append(__UpperCamelCase       )
											A      						=    -2
											A      						=    []
											A      						=    s
											A      						=    False
											A      						=    set()

											while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]       ) != 0:
																									A      						=    s
																									for node in self.graph[s]:
																																if (
																																    visited.count(node[1]       ) > 0
																																    and node[1] != parent
																																    and indirect_parents.count(node[1]       ) > 0
																																    and not on_the_way_back
																																):
																																							A      						=    len(__UpperCamelCase       ) - 1
																																							while len_stack_minus_one >= 0:
																																														if stack[len_stack_minus_one] == node[1]:
																																																					anticipating_nodes.add(node[1]       )
																																																					break
																																														else:
																																																					return True
																																if visited.count(node[1]       ) < 1:
																																							stack.append(node[1]       )
																																							visited.append(node[1]       )
																																							A      						=    node[1]
																																							break

            # check if all the children are visited
																		if s == ss:
																									stack.pop()
																									A      						=    True
																									if len(__UpperCamelCase       ) != 0:
																																A      						=    stack[len(__UpperCamelCase       ) - 1]
																		else:
																									A      						=    False
																									indirect_parents.append(__UpperCamelCase       )
																									A      						=    s
																									A      						=    ss

																		# check if se have reached the starting point
																		if len(__UpperCamelCase       ) == 0:
																									return False


				def __UpperCamelCase						(							self      :  str       )		->     int:
											return list(self.graph       )


				def __UpperCamelCase						(							self      :  List[str]						, __UpperCamelCase      :  Optional[int]=-2						, __UpperCamelCase      :  Union[str, Any]=-1       )		->     Optional[Any]:
											A      						=    time()
											self.dfs(__UpperCamelCase						, __UpperCamelCase       )
											A      						=    time()
											return end - begin


				def __UpperCamelCase						(							self      :  int						, __UpperCamelCase      :  List[Any]=-2       )		->     Optional[Any]:
											A      						=    time()
											self.bfs(__UpperCamelCase       )
											A      						=    time()
											return end - begin




import unittest
from queue import Empty
from threading import Thread

from transformers import AutoTokenizer, TextIteratorStreamer, TextStreamer, is_torch_available
from transformers.testing_utils import CaptureStdout, require_torch, torch_device

from ..test_modeling_common import ids_tensor


if is_torch_available():
				import torch

				from transformers import AutoModelForCausalLM



@require_torch
class        lowerCAmelCase__					(  unittest.TestCase       ):


				def __UpperCamelCase						(							self      :  List[Any]       )		->     Optional[Any]:
											A      						=    AutoTokenizer.from_pretrained('hf-internal-testing/tiny-random-gpt2'       )
											A      						=    AutoModelForCausalLM.from_pretrained('hf-internal-testing/tiny-random-gpt2'       ).to(__UpperCamelCase       )
											A      						=    -1

											A      						=    ids_tensor((1, 5)						, vocab_size=model.config.vocab_size       ).to(__UpperCamelCase       )
											A      						=    model.generate(__UpperCamelCase						, max_new_tokens=10						, do_sample=__UpperCamelCase       )
											A      						=    tokenizer.decode(greedy_ids[0]       )

											with CaptureStdout() as cs:
																		A      						=    TextStreamer(__UpperCamelCase       )
																		model.generate(__UpperCamelCase						, max_new_tokens=10						, do_sample=__UpperCamelCase						, streamer=__UpperCamelCase       )
											# The greedy text should be printed to stdout, except for the final "\n" in the streamer
											A      						=    cs.out[:-1]

											self.assertEqual(__UpperCamelCase						, __UpperCamelCase       )


				def __UpperCamelCase						(							self      :  int       )		->     List[Any]:
											A      						=    AutoTokenizer.from_pretrained('hf-internal-testing/tiny-random-gpt2'       )
											A      						=    AutoModelForCausalLM.from_pretrained('hf-internal-testing/tiny-random-gpt2'       ).to(__UpperCamelCase       )
											A      						=    -1

											A      						=    ids_tensor((1, 5)						, vocab_size=model.config.vocab_size       ).to(__UpperCamelCase       )
											A      						=    model.generate(__UpperCamelCase						, max_new_tokens=10						, do_sample=__UpperCamelCase       )
											A      						=    tokenizer.decode(greedy_ids[0]       )

											A      						=    TextIteratorStreamer(__UpperCamelCase       )
											A      						=    {'input_ids': input_ids, 'max_new_tokens': 10, 'do_sample': False, 'streamer': streamer}
											A      						=    Thread(target=model.generate						, kwargs=__UpperCamelCase       )
											thread.start()
											A      						=    ''
											for new_text in streamer:
																		streamer_text += new_text

											self.assertEqual(__UpperCamelCase						, __UpperCamelCase       )


				def __UpperCamelCase						(							self      :  int       )		->     Tuple:
											A      						=    AutoTokenizer.from_pretrained('hf-internal-testing/tiny-random-gpt2'       )
											A      						=    AutoModelForCausalLM.from_pretrained('hf-internal-testing/tiny-random-gpt2'       ).to(__UpperCamelCase       )
											A      						=    -1

											A      						=    ids_tensor((1, 5)						, vocab_size=model.config.vocab_size       ).to(__UpperCamelCase       )
											A      						=    model.generate(__UpperCamelCase						, max_new_tokens=10						, do_sample=__UpperCamelCase       )
											A      						=    greedy_ids[:, input_ids.shape[1] :]
											A      						=    tokenizer.decode(new_greedy_ids[0]       )

											with CaptureStdout() as cs:
																		A      						=    TextStreamer(__UpperCamelCase						, skip_prompt=__UpperCamelCase       )
																		model.generate(__UpperCamelCase						, max_new_tokens=10						, do_sample=__UpperCamelCase						, streamer=__UpperCamelCase       )
											# The greedy text should be printed to stdout, except for the final "\n" in the streamer
											A      						=    cs.out[:-1]

											self.assertEqual(__UpperCamelCase						, __UpperCamelCase       )


				def __UpperCamelCase						(							self      :  List[Any]       )		->     Tuple:
											# Tests that we can pass `decode_kwargs` to the streamer to control how the tokens are decoded. Must be tested
											# with actual models -- the dummy models' tokenizers are not aligned with their models, and
											# `skip_special_tokens=True` has no effect on them
											A      						=    AutoTokenizer.from_pretrained('distilgpt2'       )
											A      						=    AutoModelForCausalLM.from_pretrained('distilgpt2'       ).to(__UpperCamelCase       )
											A      						=    -1

											A      						=    torch.ones((1, 5)						, device=__UpperCamelCase       ).long() * model.config.bos_token_id
											with CaptureStdout() as cs:
																		A      						=    TextStreamer(__UpperCamelCase						, skip_special_tokens=__UpperCamelCase       )
																		model.generate(__UpperCamelCase						, max_new_tokens=1						, do_sample=__UpperCamelCase						, streamer=__UpperCamelCase       )

											# The prompt contains a special token, so the streamer should not print it. As such, the output text, when
											# re-tokenized, must only contain one token
											A      						=    cs.out[:-1]  # Remove the final "\n"
											A      						=    tokenizer(__UpperCamelCase						, return_tensors='pt'       )
											self.assertEqual(streamer_text_tokenized.input_ids.shape						, (1, 1)       )


				def __UpperCamelCase						(							self      :  Any       )		->     Dict:
											A      						=    AutoTokenizer.from_pretrained('hf-internal-testing/tiny-random-gpt2'       )
											A      						=    AutoModelForCausalLM.from_pretrained('hf-internal-testing/tiny-random-gpt2'       ).to(__UpperCamelCase       )
											A      						=    -1

											A      						=    ids_tensor((1, 5)						, vocab_size=model.config.vocab_size       ).to(__UpperCamelCase       )
											A      						=    TextIteratorStreamer(__UpperCamelCase						, timeout=0.0_0_1       )
											A      						=    {'input_ids': input_ids, 'max_new_tokens': 10, 'do_sample': False, 'streamer': streamer}
											A      						=    Thread(target=model.generate						, kwargs=__UpperCamelCase       )
											thread.start()

											# The streamer will timeout after 0.001 seconds, so an exception will be raised
											with self.assertRaises(__UpperCamelCase       ):
																		A      						=    ''
																		for new_text in streamer:
																									streamer_text += new_text