(********* Myutil ************)
let rec range a b = if a >= b then [] else a::(range (a+1) b)

let rec qsort ls =
  if ls = [] then []
  else
    let p, tl = (List.hd ls), (List.tl ls) in
    let left = List.filter ((>=) p) tl in
    let right = List.filter ((<) p) tl in
    (qsort left) @ p::(qsort right)

let (>>=) x f =
  match x with
  | None -> None
  | Some x -> f x

(* TODO: グラフ理論関連の自作ライブラリを実装する
   e.g. 強連結成分分解, graphの行列表現, graphの連結リスト表現, etc...
 *)


module MyIO = struct
  let rec str_of_list acc str_of =function
    | [] -> acc
    | x::[] -> (str_of x) ^ "; " ^ acc
    | x::xs -> str_of_list ((str_of x) ^ "; " ^ acc) str_of xs

  let str_of_list str_of ls = "[" ^ (str_of_list "" str_of (List.rev ls)) ^ "]"

  let str_of_pair str_of (a, b) = "(" ^ (str_of a) ^ ", " ^ (str_of b) ^ ")"

  let read_n_integers_fast n delim =
    let rec inner ct acc =
    if ct >= n then acc
    else
      let i = if ct = n-1 then Scanf.scanf "%d" (fun d -> d)
              else Scanf.scanf ("%d" ^^ delim) (fun d -> d) in
      inner (ct + 1) (i::acc)
  in inner 0 []

  let read_n_integers n delim = List.rev @@ read_n_integers_fast n delim

  let read_bits () =
    let rec inner acc =
      try
        let acc' = (Scanf.scanf "%1d" (fun i -> i::acc)) in
        inner acc'
      with e -> acc
    in List.rev @@ inner []
end

(* O(log n) version of UnionFind *)
module UnionFindInt : sig
  type t_
  type t = t_ array
  val create   : int list -> t
  val root_of  : t -> int -> int
  val unite    : t -> int -> int -> unit
  val is_same  : t -> int -> int -> bool
  val grp_of   : t -> int -> int list
  val len_of   : t -> int -> int
end = struct
  type t_ = {parent : int option; t : int; length: int}
  type t = t_ array
  let create ilist = 
    let a = Array.make (List.length ilist) {parent = None; t = 0; length = 1} in
    let rec inner ct = function
      | [] -> a
      | l::ls -> a.(ct) <- {a.(ct) with t = l}; inner (ct + 1) ls
    in inner 0 ilist
  let root_of t i = 
    let rec inner acc i = 
      match t.(i).parent with
      | None -> List.iter (fun j -> t.(j) <- {t.(j) with parent = Some i; length = t.(i).length}) acc; i
      | Some i' -> inner (i::acc) i'
    in inner [] i
  let is_same t i1 i2 = 
    if i1 = i2 then true else let r1, r2 = root_of t i1, root_of t i2 in r1 = r2
  let unite t i1 i2 =
    if is_same t i1 i2 then () else 
      let r1, r2 = root_of t i1, root_of t i2 in 
      let l' = t.(r1).length + t.(r2).length in
      t.(r2) <- { t.(r2) with parent = Some r1; length = l'};
      t.(r1) <- { t.(r1) with length = l'}
  let grp_of t i = Array.to_list t |> List.filter (fun j -> is_same t i j.t) |> List.map (fun j -> j.t)
  let len_of t i = t.(i).length
end
(********* Myutil ************)

let calc uf islands a b =
  let la, lb = UnionFindInt.len_of uf (UnionFindInt.root_of uf a), 
               UnionFindInt.len_of uf (UnionFindInt.root_of uf b) in
  la * lb

let _ =
  let n, m = Scanf.scanf "%d %d\n" (fun n m -> (n, m)) in
  let answer = Array.make (m + 1) (n * (n - 1) / 2) in
  let bridge = Array.make m (0, 0) in
  for i=0 to m - 1 do Scanf.scanf "%d %d\n" (fun a b -> bridge.(i) <- (a-1, b-1)) done;
  let islands = range 0 n in
  let uf = UnionFindInt.create islands in
  let buf = ref 0 in
  for i = m - 1 downto 0 do
    let a, b = bridge.(i) in
    (if UnionFindInt.is_same uf a b then ()
     else 
       begin
         buf := !buf + (calc uf islands a b);
         UnionFindInt.unite uf a b;
       end);
    answer.(i) <- answer.(i) - !buf
  done;
  for i = 1 to m do Printf.printf "%d\n" answer.(i) done


Measured memory_bytes: 26496