#!/usr/bin/python

from igraph import *
from random import randint
import random

edges = [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3), (3,8), (4,5), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8), (6,7), (6,8), (7,8), (1,6)]
g = Graph(edges)

mincut_value = sys.maxint
mincut_edges = None
for i in range(0, 100):
    source = randint(0, 8)
    target = randint(0, 8)
    cut = g.mincut(source, target)
    if mincut_value > cut.value:
        mincut_value = cut.value
        mincut_edges = cut.cut

print mincut_value

g.vs["label"] = range(0, 9)
g.es[mincut_edges]["color"] = "red"
plot(g)