
"""simple docstring"""



# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

_snake_case          =						TypeVar('''T''')
class        _SCREAMING_SNAKE_CASE  (  Generic[T]							):






				'''simple docstring'''



				def __init__(					self	:			Optional[Any]				,     UpperCAmelCase_	:			bool = True  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			{}  # dictionary of lists
											_lowerCAmelCase  	=			directed


				def 				__lowerCamelCase	(					self	:			Tuple				,     UpperCAmelCase_	:			T				,     UpperCAmelCase_	:			T  )		->  GraphAdjacencyList[T]:







											"""simple docstring"""




											if not self.directed:  # For undirected graphs
																		# if both source vertex and destination vertex are both present in the
																		# adjacency list, add destination vertex to source vertex list of adjacent
																		# vertices and add source vertex to destination vertex list of adjacent
																		# vertices.
																		if source_vertex in self.adj_list and destination_vertex in self.adj_list:
																									self.adj_list[source_vertex].append(UpperCAmelCase_  )
																									self.adj_list[destination_vertex].append(UpperCAmelCase_  )
																		# if only source vertex is present in adjacency list, add destination vertex
																		# to source vertex list of adjacent vertices, then create a new vertex with
																		# destination vertex as key and assign a list containing the source vertex
																		# as it's first adjacent vertex.
																		elif source_vertex in self.adj_list:
																									self.adj_list[source_vertex].append(UpperCAmelCase_  )
																									_lowerCAmelCase  	=			[source_vertex]
																		# if only destination vertex is present in adjacency list, add source vertex
																		# to destination vertex list of adjacent vertices, then create a new vertex
																		# with source vertex as key and assign a list containing the source vertex
																		# as it's first adjacent vertex.
																		elif destination_vertex in self.adj_list:
																									self.adj_list[destination_vertex].append(UpperCAmelCase_  )
																									_lowerCAmelCase  	=			[destination_vertex]
																		# if both source vertex and destination vertex are not present in adjacency
																		# list, create a new vertex with source vertex as key and assign a list
																		# containing the destination vertex as it's first adjacent vertex also
																		# create a new vertex with destination vertex as key and assign a list
																		# containing the source vertex as it's first adjacent vertex.
																		else:
																									_lowerCAmelCase  	=			[destination_vertex]
																									_lowerCAmelCase  	=			[source_vertex]
											else:  # For directed graphs
																		# if both source vertex and destination vertex are present in adjacency
																		# list, add destination vertex to source vertex list of adjacent vertices.
																		if source_vertex in self.adj_list and destination_vertex in self.adj_list:
																									self.adj_list[source_vertex].append(UpperCAmelCase_  )
																		# if only source vertex is present in adjacency list, add destination
																		# vertex to source vertex list of adjacent vertices and create a new vertex
																		# with destination vertex as key, which has no adjacent vertex
																		elif source_vertex in self.adj_list:
																									self.adj_list[source_vertex].append(UpperCAmelCase_  )
																									_lowerCAmelCase  	=			[]
																		# if only destination vertex is present in adjacency list, create a new
																		# vertex with source vertex as key and assign a list containing destination
																		# vertex as first adjacent vertex
																		elif destination_vertex in self.adj_list:
																									_lowerCAmelCase  	=			[destination_vertex]
																		# if both source vertex and destination vertex are not present in adjacency
																		# list, create a new vertex with source vertex as key and a list containing
																		# destination vertex as it's first adjacent vertex. Then create a new vertex
																		# with destination vertex as key, which has no adjacent vertex
																		else:
																									_lowerCAmelCase  	=			[destination_vertex]
																									_lowerCAmelCase  	=			[]

											return self







				def __repr__(					self	:			Tuple  )		->  str:







											"""simple docstring"""




											return pformat(self.adj_list  )








"""simple docstring"""



def 	__snake_case  (    SCREAMING_SNAKE_CASE:					str						):






							"""simple docstring"""



							_lowerCAmelCase  	=			0

							# if input_string is "aba" than new_input_string become "a|b|a"
							_lowerCAmelCase  	=			''
							_lowerCAmelCase  	=			''

							# append each character + "|" in new_string for range(0, length-1)
							for i in input_string[: len(SCREAMING_SNAKE_CASE						) - 1]:
														new_input_string += i + "|"
							# append last character
							new_input_string += input_string[-1]

							# we will store the starting and ending of previous furthest ending palindromic
							# substring
							_lowerCAmelCase	,		_lowerCAmelCase  	=			0, 0

							# length[i] shows the length of palindromic substring with center i
							_lowerCAmelCase  	=			[1 for i in range(len(SCREAMING_SNAKE_CASE						)						)]

							# for each character in new_string find corresponding palindromic string
							_lowerCAmelCase  	=			0
							for j in range(len(SCREAMING_SNAKE_CASE						)						):
														_lowerCAmelCase  	=			1 if j > r else min(length[l + r - j] // 2     ,  r - j + 1						)
														while (
														    j - k >= 0
														    and j + k < len(SCREAMING_SNAKE_CASE						)
														    and new_input_string[k + j] == new_input_string[j - k]
														):
																					k += 1

														_lowerCAmelCase  	=			2 * k - 1

														# does this string is ending after the previously explored end (that is r) ?
														# if yes the update the new r to the last index of this
														if j + k - 1 > r:
																					_lowerCAmelCase  	=			j - k + 1  # noqa: E741
																					_lowerCAmelCase  	=			j + k - 1

														# update max_length and start position
														if max_length < length[j]:
																					_lowerCAmelCase  	=			length[j]
																					_lowerCAmelCase  	=			j

    # create that string
							_lowerCAmelCase  	=			new_input_string[start - max_length // 2 : start + max_length // 2 + 1]
							for i in s:
														if i != "|":
																					output_string += i

							return output_string


if __name__ == "__main__":
	import doctest

	doctest.testmod()






