'''simple docstring'''





from collections import deque
from math import floor
from random import random
from time import time
class   _lowerCAmelCase		:







							def __init__(				self     :    Any		):
										lowerCamelCase						:Union[str, Any]						  =     {}







							def 				snake_case  (				self     :    Any	,					__snake_case     :    Optional[Any]	,					__snake_case     :    Optional[int]	,					__snake_case     :    str=1		):
										if self.graph.get(__snake_case		):
													if self.graph[u].count([w, v]		) == 0:
																self.graph[u].append([w, v]		)
										else:
													lowerCamelCase						:Dict						  =     [[w, v]]
										if not self.graph.get(__snake_case		):
													lowerCamelCase						:List[Any]						  =     []







							def 				snake_case  (				self     :    int		):
										return list(self.graph		)







							def 				snake_case  (				self     :    Union[str, Any]	,					__snake_case     :    List[Any]	,					__snake_case     :    Optional[Any]		):
										if self.graph.get(__snake_case		):
													for _ in self.graph[u]:
																if _[1] == v:
																			self.graph[u].remove(__snake_case		)







							def 				snake_case  (				self     :    Optional[int]	,					__snake_case     :    Tuple=-2	,					__snake_case     :    int=-1		):
										if s == d:
													return []
										lowerCamelCase						:int						  =     []
										lowerCamelCase						:Tuple						  =     []
										if s == -2:
													lowerCamelCase						:str						  =     list(self.graph		)[0]
										stack.append(__snake_case		)
										visited.append(__snake_case		)
										lowerCamelCase						:Dict						  =     s

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

            # check if all the children are visited
													if s == ss:
																stack.pop()
																if len(__snake_case		) != 0:
																			lowerCamelCase						:List[str]						  =     stack[len(__snake_case		) - 1]
													else:
																lowerCamelCase						:Optional[Any]						  =     ss

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







							def 				snake_case  (				self     :    Union[str, Any]	,					__snake_case     :    List[Any]=-1		):
										if c == -1:
													lowerCamelCase						:str						  =     floor(random() * 10000		) + 10
										for i in range(__snake_case		):
													# every vertex has max 100 edges
													for _ in range(floor(random() * 102		) + 1		):
																lowerCamelCase						:Dict						  =     floor(random() * c		) + 1
																if n != i:
																			self.add_pair(__snake_case	,					__snake_case	,					1		)







							def 				snake_case  (				self     :    Optional[Any]	,					__snake_case     :    str=-2		):
										lowerCamelCase						:List[str]						  =     deque()
										lowerCamelCase						:List[str]						  =     []
										if s == -2:
													lowerCamelCase						:Any						  =     list(self.graph		)[0]
										d.append(__snake_case		)
										visited.append(__snake_case		)
										while d:
													lowerCamelCase						:Optional[int]						  =     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 				snake_case  (				self     :    str	,					__snake_case     :    str		):
										lowerCamelCase						:Union[str, Any]						  =     0
										for x in self.graph:
													for y in self.graph[x]:
																if y[1] == u:
																			count += 1
										return count







							def 				snake_case  (				self     :    int	,					__snake_case     :    List[str]		):
										return len(self.graph[u]		)







							def 				snake_case  (				self     :    str	,					__snake_case     :    List[Any]=-2		):
										lowerCamelCase						:List[Any]						  =     []
										lowerCamelCase						:Dict						  =     []
										if s == -2:
													lowerCamelCase						:Union[str, Any]						  =     list(self.graph		)[0]
										stack.append(__snake_case		)
										visited.append(__snake_case		)
										lowerCamelCase						:Optional[int]						  =     s
										lowerCamelCase						:List[Any]						  =     []

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

            # check if all the children are visited
													if s == ss:
																sorted_nodes.append(stack.pop()		)
																if len(__snake_case		) != 0:
																			lowerCamelCase						:Optional[int]						  =     stack[len(__snake_case		) - 1]
													else:
																lowerCamelCase						:Union[str, Any]						  =     ss

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







							def 				snake_case  (				self     :    int		):
										lowerCamelCase						:Any						  =     []
										lowerCamelCase						:Optional[int]						  =     []
										lowerCamelCase						:Any						  =     list(self.graph		)[0]
										stack.append(__snake_case		)
										visited.append(__snake_case		)
										lowerCamelCase						:int						  =     -2
										lowerCamelCase						:Union[str, Any]						  =     []
										lowerCamelCase						:str						  =     s
										lowerCamelCase						:str						  =     False
										lowerCamelCase						:int						  =     set()

										while True:
													# check if there is any non isolated nodes
													if len(self.graph[s]		) != 0:
																lowerCamelCase						:Dict						  =     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
																			):
																						lowerCamelCase						:str						  =     len(__snake_case		) - 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]		)
																						lowerCamelCase						:Union[str, Any]						  =     node[1]
																						break

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

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







							def 				snake_case  (				self     :    Optional[Any]		):
										lowerCamelCase						:Union[str, Any]						  =     []
										lowerCamelCase						:str						  =     []
										lowerCamelCase						:List[str]						  =     list(self.graph		)[0]
										stack.append(__snake_case		)
										visited.append(__snake_case		)
										lowerCamelCase						:List[str]						  =     -2
										lowerCamelCase						:Optional[Any]						  =     []
										lowerCamelCase						:Optional[Any]						  =     s
										lowerCamelCase						:Tuple						  =     False
										lowerCamelCase						:Optional[Any]						  =     set()

										while True:
													# check if there is any non isolated nodes
													if len(self.graph[s]		) != 0:
																lowerCamelCase						:str						  =     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
																			):
																						lowerCamelCase						:List[Any]						  =     len(__snake_case		) - 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]		)
																						lowerCamelCase						:Tuple						  =     node[1]
																						break

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

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







							def 				snake_case  (				self     :    List[Any]	,					__snake_case     :    List[str]=-2	,					__snake_case     :    Optional[Any]=-1		):
										lowerCamelCase						:Union[str, Any]						  =     time()
										self.dfs(__snake_case	,					__snake_case		)
										lowerCamelCase						:Optional[Any]						  =     time()
										return end - begin







							def 				snake_case  (				self     :    int	,					__snake_case     :    int=-2		):
										lowerCamelCase						:List[Any]						  =     time()
										self.bfs(__snake_case		)
										lowerCamelCase						:Tuple						  =     time()
										return end - begin


class   _lowerCAmelCase		:







							def __init__(				self     :    Union[str, Any]		):
										lowerCamelCase						:Any						  =     {}







							def 				snake_case  (				self     :    Union[str, Any]	,					__snake_case     :    int	,					__snake_case     :    Dict	,					__snake_case     :    List[str]=1		):
										# check if the u exists
										if self.graph.get(__snake_case		):
													# 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
													lowerCamelCase						:int						  =     [[w, v]]
										# add the other way
										if self.graph.get(__snake_case		):
													# 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
													lowerCamelCase						:str						  =     [[w, u]]







							def 				snake_case  (				self     :    Tuple	,					__snake_case     :    Optional[int]	,					__snake_case     :    Tuple		):
										if self.graph.get(__snake_case		):
													for _ in self.graph[u]:
																if _[1] == v:
																			self.graph[u].remove(__snake_case		)
        # the other way round
										if self.graph.get(__snake_case		):
													for _ in self.graph[v]:
																if _[1] == u:
																			self.graph[v].remove(__snake_case		)







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

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

            # check if all the children are visited
													if s == ss:
																stack.pop()
																if len(__snake_case		) != 0:
																			lowerCamelCase						:Optional[int]						  =     stack[len(__snake_case		) - 1]
													else:
																lowerCamelCase						:Any						  =     ss

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







							def 				snake_case  (				self     :    Dict	,					__snake_case     :    List[str]=-1		):
										if c == -1:
													lowerCamelCase						:str						  =     floor(random() * 10000		) + 10
										for i in range(__snake_case		):
													# every vertex has max 100 edges
													for _ in range(floor(random() * 102		) + 1		):
																lowerCamelCase						:Optional[int]						  =     floor(random() * c		) + 1
																if n != i:
																			self.add_pair(__snake_case	,					__snake_case	,					1		)







							def 				snake_case  (				self     :    int	,					__snake_case     :    str=-2		):
										lowerCamelCase						:Optional[int]						  =     deque()
										lowerCamelCase						:List[Any]						  =     []
										if s == -2:
													lowerCamelCase						:Union[str, Any]						  =     list(self.graph		)[0]
										d.append(__snake_case		)
										visited.append(__snake_case		)
										while d:
													lowerCamelCase						:str						  =     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 				snake_case  (				self     :    int	,					__snake_case     :    Any		):
										return len(self.graph[u]		)







							def 				snake_case  (				self     :    Tuple		):
										lowerCamelCase						:Optional[int]						  =     []
										lowerCamelCase						:Optional[Any]						  =     []
										lowerCamelCase						:Any						  =     list(self.graph		)[0]
										stack.append(__snake_case		)
										visited.append(__snake_case		)
										lowerCamelCase						:Optional[Any]						  =     -2
										lowerCamelCase						:Optional[int]						  =     []
										lowerCamelCase						:int						  =     s
										lowerCamelCase						:str						  =     False
										lowerCamelCase						:List[Any]						  =     set()

										while True:
													# check if there is any non isolated nodes
													if len(self.graph[s]		) != 0:
																lowerCamelCase						:List[Any]						  =     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
																			):
																						lowerCamelCase						:Tuple						  =     len(__snake_case		) - 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]		)
																						lowerCamelCase						:Any						  =     node[1]
																						break

            # check if all the children are visited
													if s == ss:
																stack.pop()
																lowerCamelCase						:str						  =     True
																if len(__snake_case		) != 0:
																			lowerCamelCase						:Dict						  =     stack[len(__snake_case		) - 1]
													else:
																lowerCamelCase						:Tuple						  =     False
																indirect_parents.append(__snake_case		)
																lowerCamelCase						:Union[str, Any]						  =     s
																lowerCamelCase						:Any						  =     ss

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







							def 				snake_case  (				self     :    Any		):
										lowerCamelCase						:Optional[Any]						  =     []
										lowerCamelCase						:Union[str, Any]						  =     []
										lowerCamelCase						:Any						  =     list(self.graph		)[0]
										stack.append(__snake_case		)
										visited.append(__snake_case		)
										lowerCamelCase						:Any						  =     -2
										lowerCamelCase						:Dict						  =     []
										lowerCamelCase						:Dict						  =     s
										lowerCamelCase						:Union[str, Any]						  =     False
										lowerCamelCase						:List[Any]						  =     set()

										while True:
													# check if there is any non isolated nodes
													if len(self.graph[s]		) != 0:
																lowerCamelCase						:Union[str, Any]						  =     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
																			):
																						lowerCamelCase						:int						  =     len(__snake_case		) - 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]		)
																						lowerCamelCase						:Dict						  =     node[1]
																						break

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

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







							def 				snake_case  (				self     :    List[Any]		):
										return list(self.graph		)







							def 				snake_case  (				self     :    Optional[int]	,					__snake_case     :    Dict=-2	,					__snake_case     :    int=-1		):
										lowerCamelCase						:str						  =     time()
										self.dfs(__snake_case	,					__snake_case		)
										lowerCamelCase						:Tuple						  =     time()
										return end - begin







							def 				snake_case  (				self     :    List[str]	,					__snake_case     :    Union[str, Any]=-2		):
										lowerCamelCase						:List[Any]						  =     time()
										self.bfs(__snake_case		)
										lowerCamelCase						:Tuple						  =     time()
										return end - begin




def  _lowerCamelCase					(   a_				: list):

			if not grid or not grid[0]:
						raise TypeError('''The grid does not contain the appropriate information''')

			for cell_n in range(1						,			len(grid[0])):
						grid[0][cell_n] += grid[0][cell_n - 1]
			lowerCamelCase						:Any						  =     grid[0]

			for row_n in range(1						,			len(a_)):
						lowerCamelCase						:List[str]						  =     grid[row_n]
						lowerCamelCase						:Union[str, Any]						  =     fill_row(a_						,			a_)
						lowerCamelCase						:List[Any]						  =     grid[row_n]

			return grid[-1][-1]





def  _lowerCamelCase					(   a_				: list						,			a_				: list):
			current_row[0] += row_above[0]
			for cell_n in range(1						,			len(a_)):
						current_row[cell_n] += min(current_row[cell_n - 1]						,			row_above[cell_n])

			return current_row


if __name__ == "__main__":
			import doctest

			doctest.testmod()



