If $n$ is even, $n+1 \mid n^{n+1}+1$, so we can cover all odd $m$. If $m$ is even and $m \mid n^{n+1}+1$, then $n$ must be odd, so $n+1$ is even, and $m$ cannot be divisible by 4 or any prime congruent to $3(\bmod 4)$. Conversely, if $m / 2$ has all factors $1(\bmod 4)$, then by CRT there exists $N \equiv 1(\bmod 4)$ such that $m\left|N^{2}+1\right| N^{N+1}+1($ note $(N+1) / 2$ is odd $)$. So the only bad numbers take the form $2 k$, where $1 \leq k \leq 24$ is divisible by at least one of $2,3,7,11,19,23,31, \ldots$ We count $k=2,4, \ldots, 24$ (there are 12 numbers here), $k=3,9,15,21$ (another four), $k=7,11,19,23$ (another four), giving a final answer of $49-12-4-4=29$.