Inverting RSA using an oracle
This is homework, and so I won't give you the answer outright; I will give hints:

Hint 1: how could you efficiently generate a random pair $x_1, y_1$ with $x_1^e = y_1$, without resorting to the Oracle?

Hint 2: how could you use the above observation to accelerate your algorithm?