Before revision:  Eden and Rosenbaum provided upper and lower bounds of \Theta^*(n/\sqrt m) for sampling a single edge in general graphs (where O^*(\cdot) suppresses poly \poly (1/\epsilon) and poly \poly (\log n) dependencies).
After revision:  Eden and Rosenbaum provided upper and lower bounds of \Theta^*(n/\sqrt m) for sampling a single edge in general graphs (where O^*(\cdot) suppresses poly \poly (1/\epsilon) and \poly (\log n) dependencies).