Give you an undirected graph with no guarantee of connectivity, Erase 2 edges to minimize the maximum connected block. You only need to output The size of the largest connected block.

How to solve it in less than O(N^2) Time Complexity ?

Sorry of my suck English :(

UPD: We have found an another O(N^2) Algorithm. We can check all edges, try to delete the edges that we are checking, and then use the Tarjan algorithm for the remaining edges. Perhaps optimizing this algorithm can reduces time complexity.