Breaking ElGammal encryption of two different mesagges
Further hint: suppose we computed $q = (p-1)/2^\lambda$ odd, and given $(u_1, v_1) = (g^r, m y^r)$, we compute $(g^r)^q, (m y^r)^q$.  Once we have done that, how can you distinguish the $m=1$ and $m= -1$ cases?