Choosing a random edge with restrictions
You can't.  Consider the bipartite graph with a single edge $(u_0,v_0)$, with $u_0,v_0$ randomly chosen at time of creation of the graph.  Then sampling from $U$ has only a $1/2^n$ chance to hit $u_0$ each time, and sampling from $V$ has only a $1/2^n$ chance to hit $v_0$ each time, so you need exponentially many samples before you can find that edge.

In particular, after making $q$ samples, there is at most a $q/2^n$ chance that you receive either $u_0$ or $v_0$.  Without sampling either $u_0$ or $v_0$ you have no hope of outputting the edge $(u_0,v_0)$.  So after polynomially many samples, there's only an exponentially small chance of outputting that edge.  Yet a correct algorithm must always output that edge every time.  So in general, there's no way to solve your problem, or even to output from a distribution close to the desired one.