Quickly identify changes in connectivity
You can work your way backwards. Suppose the edges being removed are $e_1,\ldots,e_\ell$, and the rest of the edges form a set $E$. Start by determining the connected components induced by $E$, using a disjoint sets data structure. Now add the edges $e_\ell,\ldots,e_1$ in that order, updating the disjoint sets data structure, until $u$ and $v$ belong to the same connected component. The last edge encountered in this way is the one you seek.