class RandomizedGlobalMinCut; end
class << RandomizedGlobalMinCut
  private
  def make_graph_representation(es)
    ve = {}; ev = {}; v_living = []; e_living = []; v_max = -1
    es.each.with_index do |vs,i|
      v0,v1 = vs
      ve[v0] ? (ve[v0] << i):(ve[v0] = [i])
      ve[v1] ? (ve[v1] << i):(ve[v1] = [i])
      ev[i] = [v0,v1]
      v_living << v0; v_living << v1; e_living << i
      m = [v0,v1].max
      v_max = m if v_max < m
    end
    [ve,ev,v_living.uniq,e_living,v_max]
  end
  def calc_main(g)
    ve,ev,v_living,e_living,v_max = g
    closure = {}
    v_living.each do |v|
      closure[v] = [v]
    end
    while v_living.length > 2
      e = e_living[Random.rand(e_living.length)]
      v0,v1 = ev[e]
      v = v_max+1
      [v0,v1].each do |w|
        ve[w].each do |f|
          ev[f].map!{|x| x == w ? v : x}
        end
      end
      ve[v] = (ve[v0].select{|x|x!=e} + ve[v1].select{|x|x!=e}).uniq
      ve.delete(v0); ve.delete(v1); ev.delete(e)
      v_living = v_living - [v0,v1] + [v]
      e_living = e_living - [e]
      closure[v] = (closure[v0] + closure[v1]).uniq
      v_max += 1
    end
    v0,v1 = v_living
    [closure[v0],closure[v1]]
  end
  def cut_val(es, cut)
    count = 0
    es.each do |e|
      count += 1 if cut[0].include?(e[0]) && cut[1].include?(e[1]) || cut[1].include?(e[0]) && cut[0].include?(e[1])
    end
    count
  end
  public
  def calc(es)
    g = make_graph_representation(es)
    vn = g[2].length
    iter_n = ((vn*(vn-1)/2)*Math.log(vn)).ceil
    min_cut = nil
    min_val = 10**10
    iter_n.times do
      g = make_graph_representation(es)
      cut = calc_main(g)
      val = cut_val(es,cut)
      if val < min_val
        min_val = val
        min_cut = cut
      end
    end
    [min_val,min_cut]
  end
end

def k_n(n)
  es = []
  (0...n).each do |j|
    (j...n).each do |i|
      es << [i,j] if i != j
    end
  end
  es
end

if __FILE__ == $0
  p RandomizedGlobalMinCut::calc(k_n(13))
end