


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







class        lowerCamelCase__	:






   """simple docstring"""






   def __init__(							self     ):

      '''simple docstring'''


      UpperCamelCase__					=       {}




   def 				snake_case__				(							self      ,						snake_case      ,						snake_case      ,						snake_case=1     ):

      '''simple docstring'''


      if self.graph.get(snake_case     ):
         if self.graph[u].count([w, v]     ) == 0:
            self.graph[u].append([w, v]     )
      else:
         UpperCamelCase__					=       [[w, v]]
      if not self.graph.get(snake_case     ):
         UpperCamelCase__					=       []




   def 				snake_case__				(							self     ):

      '''simple docstring'''


      return list(self.graph     )




   def 				snake_case__				(							self      ,						snake_case      ,						snake_case     ):

      '''simple docstring'''


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




   def 				snake_case__				(							self      ,						snake_case=-2      ,						snake_case=-1     ):

      '''simple docstring'''


      if s == d:
         return []
      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      if s == -2:
         UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       s

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

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

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




   def 				snake_case__				(							self      ,						snake_case=-1     ):

      '''simple docstring'''


      if c == -1:
         UpperCamelCase__					=       floor(random() * 10000     ) + 10
      for i in range(snake_case     ):
         # every vertex has max 100 edges
         for _ in range(floor(random() * 102     ) + 1     ):
            UpperCamelCase__					=       floor(random() * c     ) + 1
            if n != i:
               self.add_pair(snake_case      ,						snake_case      ,						1     )




   def 				snake_case__				(							self      ,						snake_case=-2     ):

      '''simple docstring'''


      UpperCamelCase__					=       deque()
      UpperCamelCase__					=       []
      if s == -2:
         UpperCamelCase__					=       list(self.graph     )[0]
      d.append(snake_case     )
      visited.append(snake_case     )
      while d:
         UpperCamelCase__					=       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      ,						snake_case     ):

      '''simple docstring'''


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




   def 				snake_case__				(							self      ,						snake_case     ):

      '''simple docstring'''


      return len(self.graph[u]     )




   def 				snake_case__				(							self      ,						snake_case=-2     ):

      '''simple docstring'''


      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      if s == -2:
         UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       s
      UpperCamelCase__					=       []

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

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

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




   def 				snake_case__				(							self     ):

      '''simple docstring'''


      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       -2
      UpperCamelCase__					=       []
      UpperCamelCase__					=       s
      UpperCamelCase__					=       False
      UpperCamelCase__					=       set()

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

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

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




   def 				snake_case__				(							self     ):

      '''simple docstring'''


      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       -2
      UpperCamelCase__					=       []
      UpperCamelCase__					=       s
      UpperCamelCase__					=       False
      UpperCamelCase__					=       set()

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

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

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




   def 				snake_case__				(							self      ,						snake_case=-2      ,						snake_case=-1     ):

      '''simple docstring'''


      UpperCamelCase__					=       time()
      self.dfs(snake_case      ,						snake_case     )
      UpperCamelCase__					=       time()
      return end - begin







   def 				snake_case__				(							self      ,						snake_case=-2     ):

      '''simple docstring'''


      UpperCamelCase__					=       time()
      self.bfs(snake_case     )
      UpperCamelCase__					=       time()
      return end - begin







class        lowerCamelCase__	:






   """simple docstring"""






   def __init__(							self     ):

      '''simple docstring'''


      UpperCamelCase__					=       {}




   def 				snake_case__				(							self      ,						snake_case      ,						snake_case      ,						snake_case=1     ):

      '''simple docstring'''


      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
         UpperCamelCase__					=       [[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
         UpperCamelCase__					=       [[w, u]]




   def 				snake_case__				(							self      ,						snake_case      ,						snake_case     ):

      '''simple docstring'''


      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      ,						snake_case=-2      ,						snake_case=-1     ):

      '''simple docstring'''


      if s == d:
         return []
      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      if s == -2:
         UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       s

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

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

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




   def 				snake_case__				(							self      ,						snake_case=-1     ):

      '''simple docstring'''


      if c == -1:
         UpperCamelCase__					=       floor(random() * 10000     ) + 10
      for i in range(snake_case     ):
         # every vertex has max 100 edges
         for _ in range(floor(random() * 102     ) + 1     ):
            UpperCamelCase__					=       floor(random() * c     ) + 1
            if n != i:
               self.add_pair(snake_case      ,						snake_case      ,						1     )




   def 				snake_case__				(							self      ,						snake_case=-2     ):

      '''simple docstring'''


      UpperCamelCase__					=       deque()
      UpperCamelCase__					=       []
      if s == -2:
         UpperCamelCase__					=       list(self.graph     )[0]
      d.append(snake_case     )
      visited.append(snake_case     )
      while d:
         UpperCamelCase__					=       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      ,						snake_case     ):

      '''simple docstring'''


      return len(self.graph[u]     )




   def 				snake_case__				(							self     ):

      '''simple docstring'''


      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       -2
      UpperCamelCase__					=       []
      UpperCamelCase__					=       s
      UpperCamelCase__					=       False
      UpperCamelCase__					=       set()

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

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

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




   def 				snake_case__				(							self     ):

      '''simple docstring'''


      UpperCamelCase__					=       []
      UpperCamelCase__					=       []
      UpperCamelCase__					=       list(self.graph     )[0]
      stack.append(snake_case     )
      visited.append(snake_case     )
      UpperCamelCase__					=       -2
      UpperCamelCase__					=       []
      UpperCamelCase__					=       s
      UpperCamelCase__					=       False
      UpperCamelCase__					=       set()

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

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

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




   def 				snake_case__				(							self     ):

      '''simple docstring'''


      return list(self.graph     )




   def 				snake_case__				(							self      ,						snake_case=-2      ,						snake_case=-1     ):

      '''simple docstring'''


      UpperCamelCase__					=       time()
      self.dfs(snake_case      ,						snake_case     )
      UpperCamelCase__					=       time()
      return end - begin







   def 				snake_case__				(							self      ,						snake_case=-2     ):

      '''simple docstring'''


      UpperCamelCase__					=       time()
      self.bfs(snake_case     )
      UpperCamelCase__					=       time()
      return end - begin






from typing import Any







class        lowerCamelCase__	:






			"""simple docstring"""






			def __init__(							self      ,						snake_case     ):

						'''simple docstring'''


						UpperCamelCase__					=       data
						UpperCamelCase__					=       None







class        lowerCamelCase__	:






			"""simple docstring"""






			def __init__(							self     ):

						'''simple docstring'''


						UpperCamelCase__					=       None




			def 				snake_case__				(							self     ):

						'''simple docstring'''


						UpperCamelCase__					=       self.head
						while temp is not None:
									print(temp.data      ,						end=" "     )
									UpperCamelCase__					=       temp.next
						print()




			def 				snake_case__				(							self      ,						snake_case     ):

						'''simple docstring'''


						UpperCamelCase__					=       Node(snake_case     )
						UpperCamelCase__					=       self.head
						UpperCamelCase__					=       new_node







			def 				snake_case__				(							self      ,						snake_case      ,						snake_case     ):

						'''simple docstring'''


						if node_data_a == node_data_a:
									return
						else:
									UpperCamelCase__					=       self.head
									while node_a is not None and node_a.data != node_data_a:
												UpperCamelCase__					=       node_a.next

									UpperCamelCase__					=       self.head
									while node_a is not None and node_a.data != node_data_a:
												UpperCamelCase__					=       node_a.next

									if node_a is None or node_a is None:
												return

									UpperCamelCase__,      UpperCamelCase__					=       node_a.data, node_a.data


if __name__ == "__main__":
						__UpperCamelCase    		=       LinkedList()
						for i in range(5, 0, -1):
												ll.push(i)

						ll.print_list()

						ll.swap_nodes(1, 4)
						print('After swapping')
						ll.print_list()


