#! /usr/bin/env ruby

require 'set'

if ARGV.length != 1
    abort("Incorrect arguments - needs input file")
elsif not File.exist? (ARGV[0])
abort("File #{ARGV[0]} did not exist")
end

file = ARGV[0]


connections = File.open(file, "r").each_line(chomp: true).flat_map do |line|
    node1, rest = line.split(": ")
    rest.split(" ").flat_map {|node| [[node1,node], [node,node1]]}
end.group_by {|key, value| key}.transform_values {|vals| vals.map {|val| [val[1], 1]}.to_h}

puts "#{connections}"

# From https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm
# and https://tjkendev.github.io/procon-library/python/graph/stoer-wagner-algorithm.html

def global_minimum_cut(graph, u0)
    N = graph.size
    res = 10**18

    # groups = [{i} for i in range(N)]

    merged = [0]*N
    for s in range(N-1):
        # minimum cut phase
        used = [0]*N
        used[u0] = 1
        costs = [0]*N
        for v in range(N):
            if E[u0][v] != -1:
                costs[v] = E[u0][v]
        order = []
        for _ in range(N-1-s):
            v = mc = -1
            for i in range(N):
                if used[i] or merged[i]:
                    continue
                if mc < costs[i]:
                    mc = costs[i]
                    v = i
            # assert v != -1

            # v: the most tightly connected vertex
            for w in range(N):
                if used[w] or E[v][w] == -1:
                    continue
                costs[w] += E[v][w]
            used[v] = 1
            order.append(v)

        v = order[-1]
        ws = 0
        for w in range(N):
            if E[v][w] != -1:
                ws += E[v][w]
        # - the current min-cut is (groups[v], V - groups[v])
        # - the weight of the cut is ws
        res = min(res, ws)

        if len(order) > 1:
            u = order[-2]
            # groups[u].update(groups[v])
            # groups[v] = None

            # merge u and v
            merged[v] = 1
            for w in range(N):
                if w != u:
                    if E[v][w] == -1:
                        continue
                    if E[u][w] != -1:
                        E[u][w] = E[w][u] = E[u][w] + E[v][w]
                    else:
                        E[u][w] = E[w][u] = E[v][w]
                E[v][w] = E[w][v] = -1
    return res

puts global_minimum_cut(connections, 1)