Suppose G is a connected graph on 100 vertices with 500 edges, every vertex of degree 10.
If you apply the randomized min cut algorithm to this graph, how many contractions are performed before the algorithm terminates?