Show that this language is in NP $\cap$ coNP

Question

Say $\ell: \{0,1\}^\ast \to \{0,1\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\{v \;\Big|\; \exists u: \bigl(u_1 = 1 ~~\text{and}~~ \ell(u) = v\bigr) \Bigr\}.$$ How do I prove that $L$ is in $\mathsf{NP} \cap \mathsf{coNP}$? Basically, what would appropriate witnesses for $L$ in $\mathsf{NP}$ and $\mathsf{coNP}$ be?

Answer 1

Hint: Use the fact that $\ell$ is one-to-one, and so to every $v$ there corresponds a unique $u$ such that $\ell(u) = v$.