output_description: In the order i = 1, 2, ..., M, print the inconvenience just after the i-th
  bridge collapses. Note that the answer may not fit into a 32-bit integer type.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 B_1
      A_2 B_2
      \vdots
      A_M B_M
attempt: # -*- coding: utf-8 -*-
  import sys
  
  # ----------------------------------------------------------------
  # Use Solve Function
  
  
  def solve(lines):
      N, M = map(int, lines.pop(0).split(" "))
      NLIST = []
      for i in range(M):
          A, B = map(int, lines.pop(0).split(" "))
          NLIST.append((A, B))
  
      res = N * (N - 1) // 2
      R = [res]
      sets = []
  
      for i in range(M - 1, 0, -1):
          x = NLIST[i]
          print(x)
          n1 = {x[0]}
          n2 = {x[1]}
  
          delete_idx = []
  
          for j, y in enumerate(sets):
              if x[0] in y:
                  n1 = y
                  delete_idx.append(j)
              if x[1] in y:
                  n2 = y
                  if not j in delete_idx:
                      delete_idx.append(j)
  
          delete_idx.sort(reverse=True)
          for k in delete_idx:
              sets.pop(k)
  
          if n1 != n2:
              res -= len(n1) * len(n2)
              n1 = n1.union(n2)
  
          sets.append(n1)
          R.append(res)
  
      print(R)
  
  
  lines = [x.strip() for x in sys.stdin.readlines()]
  
  #
  # solve !!
  #
  solve(lines)
  
problem_description: Statement
  
  There are N islands and M bridges.
  
  The i-th bridge connects the A_i-th and B_i-th islands bidirectionally.
  
  Initially, we can travel between any two islands using some of these bridges.
  
  However, the results of a survey show that these bridges will all collapse
  because of aging, in the order from the first bridge to the M-th bridge.
  
  Let the **inconvenience** be the number of pairs of islands (a, b) (a < b)
  such that we are no longer able to travel between the a-th and b-th islands
  using some of the bridges remaining.
  
  For each i (1 \leq i \leq M), find the inconvenience just after the i-th
  bridge collapses.
samples: [{"input": "4 5\n    1 2\n    3 4\n    1 3\n    2 3\n    1 4", "output": "0\n    0\n    4\n    5\n    6\n    \n\nFor example, when the first to third bridges have collapsed, the inconvenience\nis 4 since we can no longer travel between the pairs (1, 2), (1, 3), (2, 4)\nand (3, 4).\n\n* * *"}, {"input": "6 5\n    2 3\n    1 2\n    5 6\n    3 4\n    4 5", "output": "8\n    9\n    12\n    14\n    15\n    \n\n* * *"}, {"input": "2 1\n    1 2", "output": "1"}]