


'''simple docstring'''




from __future__ import annotations

from PIL import Image

# Define glider example
__snake_case    						=[
    [0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
]

# Define blinker example
__snake_case    						=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]





def 	a_					( lowerCamelCase	:     list[list[int]]				):
   lowerCAmelCase     =			[]
   for i in range(len(lowerCamelCase				)				):
      lowerCAmelCase     =			[]
      for j in range(len(cells[i]				)				):
         # Get the number of live neighbours
         lowerCAmelCase     =			0
         if i > 0 and j > 0:
            neighbour_count += cells[i - 1][j - 1]
         if i > 0:
            neighbour_count += cells[i - 1][j]
         if i > 0 and j < len(cells[i]				) - 1:
            neighbour_count += cells[i - 1][j + 1]
         if j > 0:
            neighbour_count += cells[i][j - 1]
         if j < len(cells[i]				) - 1:
            neighbour_count += cells[i][j + 1]
         if i < len(lowerCamelCase				) - 1 and j > 0:
            neighbour_count += cells[i + 1][j - 1]
         if i < len(lowerCamelCase				) - 1:
            neighbour_count += cells[i + 1][j]
         if i < len(lowerCamelCase				) - 1 and j < len(cells[i]				) - 1:
            neighbour_count += cells[i + 1][j + 1]

         # Rules of the game of life (excerpt from Wikipedia):
         # 1. Any live cell with two or three live neighbours survives.
         # 2. Any dead cell with three live neighbours becomes a live cell.
         # 3. All other live cells die in the next generation.
         #    Similarly, all other dead cells stay dead.
         lowerCAmelCase     =			cells[i][j] == 1
         if (
             (alive and 2 <= neighbour_count <= 3)
             or not alive
             and neighbour_count == 3
         ):
            next_generation_row.append(1				)
         else:
            next_generation_row.append(0				)

      next_generation.append(lowerCamelCase				)
   return next_generation





def 	a_					( lowerCamelCase	:     list[list[int]]	, lowerCamelCase	:     int				):
   lowerCAmelCase     =			[]
   for _ in range(lowerCamelCase				):
      # Create output image
      lowerCAmelCase     =			Image.new('RGB'	, (len(cells[0]				), len(lowerCamelCase				))				)
      lowerCAmelCase     =			img.load()

      # Save cells to image
      for x in range(len(lowerCamelCase				)				):
         for y in range(len(cells[0]				)				):
            lowerCAmelCase     =			255 - cells[y][x] * 255
            lowerCAmelCase     =			(colour, colour, colour)

        # Save image
      images.append(lowerCamelCase				)
      lowerCAmelCase     =			new_generation(lowerCamelCase				)
   return images


if __name__ == "__main__":
       __snake_case    						=generate_images(GLIDER, 16)
       images[0].save("""out.gif""", save_all=True, append_images=images[1:])









'''simple docstring'''




def 	a_					( lowerCamelCase	:     Optional[Any]				):
   return [
       {
           0: [1, 2],
           1: [0, 2],
           2: [0, 1, 3, 5],
           3: [2, 4],
           4: [3],
           5: [2, 6, 8],
           6: [5, 7],
           7: [6, 8],
           8: [5, 7],
       },
       {
           0: [6],
           1: [9],
           2: [4, 5],
           3: [4],
           4: [2, 3],
           5: [2],
           6: [0, 7],
           7: [6],
           8: [],
           9: [1],
       },
       {
           0: [4],
           1: [6],
           2: [],
           3: [5, 6, 7],
           4: [0, 6],
           5: [3, 8, 9],
           6: [1, 3, 4, 7],
           7: [3, 6, 8, 9],
           8: [5, 7],
           9: [5, 7],
       },
       {
           0: [1, 3],
           1: [0, 2, 4],
           2: [1, 3, 4],
           3: [0, 2, 4],
           4: [1, 2, 3],
       },
   ][index]





def 	a_					( lowerCamelCase	:     dict[int, list[int]]				):
   lowerCAmelCase     =			0
   lowerCAmelCase     =			len(lowerCamelCase				)  # No of vertices in graph
   lowerCAmelCase     =			[0] * n
   lowerCAmelCase     =			[False] * n

   def dfs(lowerCamelCase	:     Tuple	, lowerCamelCase	:     str	, lowerCamelCase	:     Dict	, lowerCamelCase	:     str				):
      lowerCAmelCase     =			True
      lowerCAmelCase     =			id_
      id_ += 1
      for to in graph[at]:
         if to == parent:
            pass
         elif not visited[to]:
            dfs(lowerCamelCase	, lowerCamelCase	, lowerCamelCase	, id_				)
            lowerCAmelCase     =			min(low[at]	, low[to]				)
            if id_ <= low[to]:
               bridges.append((at, to) if at < to else (to, at)				)
         else:
            # This edge is a back edge and cannot be a bridge
            lowerCAmelCase     =			min(low[at]	, low[to]				)

   lowerCAmelCase     =			[]
   for i in range(lowerCamelCase				):
      if not visited[i]:
         dfs(lowerCamelCase	, -1	, lowerCamelCase	, id_				)
   return bridges


if __name__ == "__main__":
       import doctest

       doctest.testmod()





