I claim the answer is 666. Achievability. Let $(b_1,\dots,b_{333}) = (667,668,\dots,999)$. For each $C_1,\dots,C_{666}$, write $1,2,\dots,666$ to the front side. Next, write $b_1$ to back of $C_1,C_2$, $b_2$ to back of $C_3,C_4$, and similarly $b_i$ to back of $C_{2i-1},C_{2i}$. This construction clearly works. Necessity that $m\ge 666$. I now show $m\ge 666$. For this, suppose there is a card $C_i$ with front $F_i$ and back $B_i$ such that both $F_i$ and $B_i$ appears exactly once in the deck. Then clearly $(F_i,B_i)$ cannot be realized. For this reason, it is the case that for every card, one of the numbers on it should appear once more elsewhere in the deck. Note that, using this one can exhaust a total of at most $m+m/2=3m/2$ numbers. Notice, furthermore, that this number should be at least $999$: $3m/2\ge 999\implies m\ge 666$. The example is above.