



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







class 		snake_case						:



   '''simple docstring'''






   def __init__(					self							:			Tuple)				->				Tuple:

    """simple docstring"""







    _snake_case    :  Tuple					=					{}

   def      UpperCamelCase_  (					self							:			str				,		lowerCAmelCase							:			Dict				,		lowerCAmelCase							:			Optional[int]				,		lowerCAmelCase							:			List[str]=1)				->				Union[str, Any]:

    """simple docstring"""







    if self.graph.get(A__):
     if self.graph[u].count([w, v]) == 0:
      self.graph[u].append([w, v])
    else:
     _snake_case    :  Union[str, Any]					=					[[w, v]]
    if not self.graph.get(A__):
     _snake_case    :  List[Any]					=					[]

   def      UpperCamelCase_  (					self							:			Any)				->				List[str]:

    """simple docstring"""







    return list(self.graph)

   def      UpperCamelCase_  (					self							:			Union[str, Any]				,		lowerCAmelCase							:			Dict				,		lowerCAmelCase							:			List[str])				->				Optional[int]:

    """simple docstring"""







    if self.graph.get(A__):
     for _ in self.graph[u]:
      if _[1] == v:
       self.graph[u].remove(A__)

   def      UpperCamelCase_  (					self							:			int				,		lowerCAmelCase							:			List[Any]=-2				,		lowerCAmelCase							:			List[str]=-1)				->				Union[str, Any]:

    """simple docstring"""







    if s == d:
     return []
    _snake_case    :  Dict					=					[]
    _snake_case    :  Optional[Any]					=					[]
    if s == -2:
     _snake_case    :  str					=					list(self.graph)[0]
    stack.append(A__)
    visited.append(A__)
    _snake_case    :  int					=					s

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

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

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

   def      UpperCamelCase_  (					self							:			str				,		lowerCAmelCase							:			Dict=-1)				->				Tuple:

    """simple docstring"""







    if c == -1:
     _snake_case    :  List[str]					=					floor(random() * 1_0000) + 10
    for i in range(A__):
     # every vertex has max 100 edges
     for _ in range(floor(random() * 102) + 1):
      _snake_case    :  Optional[Any]					=					floor(random() * c) + 1
      if n != i:
       self.add_pair(A__				,		A__				,		1)

   def      UpperCamelCase_  (					self							:			Union[str, Any]				,		lowerCAmelCase							:			List[Any]=-2)				->				int:

    """simple docstring"""







    _snake_case    :  Any					=					deque()
    _snake_case    :  List[str]					=					[]
    if s == -2:
     _snake_case    :  Optional[int]					=					list(self.graph)[0]
    d.append(A__)
    visited.append(A__)
    while d:
     _snake_case    :  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      UpperCamelCase_  (					self							:			str				,		lowerCAmelCase							:			Optional[Any])				->				Optional[Any]:

    """simple docstring"""







    _snake_case    :  Any					=					0
    for x in self.graph:
     for y in self.graph[x]:
      if y[1] == u:
       count += 1
    return count

   def      UpperCamelCase_  (					self							:			str				,		lowerCAmelCase							:			List[Any])				->				List[Any]:

    """simple docstring"""







    return len(self.graph[u])

   def      UpperCamelCase_  (					self							:			Union[str, Any]				,		lowerCAmelCase							:			List[str]=-2)				->				Any:

    """simple docstring"""







    _snake_case    :  List[str]					=					[]
    _snake_case    :  Optional[int]					=					[]
    if s == -2:
     _snake_case    :  Any					=					list(self.graph)[0]
    stack.append(A__)
    visited.append(A__)
    _snake_case    :  List[Any]					=					s
    _snake_case    :  Tuple					=					[]

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

          # check if all the children are visited
     if s == ss:
      sorted_nodes.append(stack.pop())
      if len(A__) != 0:
       _snake_case    :  Dict					=					stack[len(A__) - 1]
     else:
      _snake_case    :  Optional[Any]					=					ss

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

   def      UpperCamelCase_  (					self							:			Any)				->				Optional[Any]:

    """simple docstring"""







    _snake_case    :  Dict					=					[]
    _snake_case    :  int					=					[]
    _snake_case    :  Any					=					list(self.graph)[0]
    stack.append(A__)
    visited.append(A__)
    _snake_case    :  int					=					-2
    _snake_case    :  Any					=					[]
    _snake_case    :  Dict					=					s
    _snake_case    :  List[Any]					=					False
    _snake_case    :  Any					=					set()

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

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

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

   def      UpperCamelCase_  (					self							:			List[Any])				->				Any:

    """simple docstring"""







    _snake_case    :  Tuple					=					[]
    _snake_case    :  Any					=					[]
    _snake_case    :  List[Any]					=					list(self.graph)[0]
    stack.append(A__)
    visited.append(A__)
    _snake_case    :  Optional[Any]					=					-2
    _snake_case    :  Any					=					[]
    _snake_case    :  str					=					s
    _snake_case    :  List[str]					=					False
    _snake_case    :  List[Any]					=					set()

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

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

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

   def      UpperCamelCase_  (					self							:			int				,		lowerCAmelCase							:			Optional[Any]=-2				,		lowerCAmelCase							:			Union[str, Any]=-1)				->				Optional[int]:

    """simple docstring"""







    _snake_case    :  Tuple					=					time()
    self.dfs(A__				,		A__)
    _snake_case    :  Optional[int]					=					time()
    return end - begin


   def      UpperCamelCase_  (					self							:			Optional[int]				,		lowerCAmelCase							:			List[Any]=-2)				->				List[str]:

    """simple docstring"""







    _snake_case    :  List[str]					=					time()
    self.bfs(A__)
    _snake_case    :  str					=					time()
    return end - begin







class 		snake_case						:



   '''simple docstring'''






   def __init__(					self							:			Tuple)				->				List[Any]:

    """simple docstring"""







    _snake_case    :  str					=					{}

   def      UpperCamelCase_  (					self							:			List[str]				,		lowerCAmelCase							:			Optional[Any]				,		lowerCAmelCase							:			str				,		lowerCAmelCase							:			Dict=1)				->				Dict:

    """simple docstring"""







    if self.graph.get(A__):
     # 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
     _snake_case    :  Optional[int]					=					[[w, v]]
    # add the other way
    if self.graph.get(A__):
     # 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
     _snake_case    :  Tuple					=					[[w, u]]

   def      UpperCamelCase_  (					self							:			Any				,		lowerCAmelCase							:			Union[str, Any]				,		lowerCAmelCase							:			str)				->				Tuple:

    """simple docstring"""







    if self.graph.get(A__):
     for _ in self.graph[u]:
      if _[1] == v:
       self.graph[u].remove(A__)
      # the other way round
    if self.graph.get(A__):
     for _ in self.graph[v]:
      if _[1] == u:
       self.graph[v].remove(A__)

   def      UpperCamelCase_  (					self							:			List[str]				,		lowerCAmelCase							:			int=-2				,		lowerCAmelCase							:			Union[str, Any]=-1)				->				Optional[Any]:

    """simple docstring"""







    if s == d:
     return []
    _snake_case    :  List[str]					=					[]
    _snake_case    :  List[Any]					=					[]
    if s == -2:
     _snake_case    :  int					=					list(self.graph)[0]
    stack.append(A__)
    visited.append(A__)
    _snake_case    :  int					=					s

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

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

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

   def      UpperCamelCase_  (					self							:			Optional[Any]				,		lowerCAmelCase							:			Optional[Any]=-1)				->				List[str]:

    """simple docstring"""







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

   def      UpperCamelCase_  (					self							:			Dict				,		lowerCAmelCase							:			List[Any]=-2)				->				Optional[Any]:

    """simple docstring"""







    _snake_case    :  Tuple					=					deque()
    _snake_case    :  Optional[int]					=					[]
    if s == -2:
     _snake_case    :  Optional[int]					=					list(self.graph)[0]
    d.append(A__)
    visited.append(A__)
    while d:
     _snake_case    :  Dict					=					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							:			Union[str, Any]				,		lowerCAmelCase							:			Dict)				->				str:

    """simple docstring"""







    return len(self.graph[u])

   def      UpperCamelCase_  (					self							:			Any)				->				int:

    """simple docstring"""







    _snake_case    :  int					=					[]
    _snake_case    :  Any					=					[]
    _snake_case    :  Optional[Any]					=					list(self.graph)[0]
    stack.append(A__)
    visited.append(A__)
    _snake_case    :  List[Any]					=					-2
    _snake_case    :  List[Any]					=					[]
    _snake_case    :  Optional[Any]					=					s
    _snake_case    :  Any					=					False
    _snake_case    :  Dict					=					set()

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

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

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

   def      UpperCamelCase_  (					self							:			int)				->				Union[str, Any]:

    """simple docstring"""







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

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

          # check if all the children are visited
     if s == ss:
      stack.pop()
      _snake_case    :  Dict					=					True
      if len(A__) != 0:
       _snake_case    :  List[str]					=					stack[len(A__) - 1]
     else:
      _snake_case    :  List[str]					=					False
      indirect_parents.append(A__)
      _snake_case    :  List[str]					=					s
      _snake_case    :  Optional[int]					=					ss

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

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

    """simple docstring"""







    return list(self.graph)

   def      UpperCamelCase_  (					self							:			str				,		lowerCAmelCase							:			Dict=-2				,		lowerCAmelCase							:			List[str]=-1)				->				List[str]:

    """simple docstring"""







    _snake_case    :  Tuple					=					time()
    self.dfs(A__				,		A__)
    _snake_case    :  int					=					time()
    return end - begin


   def      UpperCamelCase_  (					self							:			Dict				,		lowerCAmelCase							:			Union[str, Any]=-2)				->				int:

    """simple docstring"""







    _snake_case    :  Tuple					=					time()
    self.bfs(A__)
    _snake_case    :  List[Any]					=					time()
    return end - begin










from math import ceil, sqrt



def       lowercase       (   SCREAMING_SNAKE_CASE__       :	int = 1_000_000				)  ->     int:
 _snake_case    :  Tuple					=					0

 for outer_width in range(3				,       (limit // 4) + 2				):
  if outer_width**2 > limit:
   _snake_case    :  int					=					max(ceil(sqrt(outer_width**2 - limit				)				)				,       1				)
  else:
   _snake_case    :  Any					=					1
  if (outer_width - hole_width_lower_bound) % 2:
   hole_width_lower_bound += 1

  answer += (outer_width - hole_width_lower_bound - 2) // 2 + 1

 return answer


if __name__ == "__main__":
  print(F'''{solution() = }''')
