Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges. Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific order. Suppose that we remove the edges from $G$ one at a time, in this order. Initially, the graph is connected, and at the end of this process the graph is disconnected. Therefore, there is an edge $e_i$ such that just before removing $e_i$ the graph has at least one connected component with more than $n/4$ nodes, but after removing $e_i$ every connected component of the graph has at most $n/4$ nodes.
Give an efficient algorithm that determines this edge $e_i$. Assume that $G$ is given to the algorithm as a plain linked list of the edges appearing in the order $e_1, e_2, \dots, e_m$. The worst-case running time of this algorithm must be asymptotically better than $O(mn)$.