Note that $m < n$ due to size (assume $m \geq n$) since else$m^n - n > n^n - n > n!$ for $n \geq 3$, and $m^n - n > m$, then $(m^n - n)^m > m + n!$ (the cases $n = 1, 2$ and $m = 1$ are left to the reader). So, $m \mid n!$. Consider a prime $q$ such that $q \mid m$, if $v_q(n!) > v_q(m)$, then $v_q(n! + m) = v_q(m)$, $v_q(m^n - n) = v_q(n)$, so $mv_q(n) = v_q(m)$, a clear contradiction as $v_q(m) < m$. So, $v_q(n!) = v_q(m)$, and if $m$ is not $q$ itself, then there will exist a smaller multiple of $q$ less than $m$ which is also less than $n$, meaning that $v_q(n!) > v_q(m)$. Therefore, $m$ is prime. But, then $m \mid n$, and if $n \geq 2m$, then $v_m(n!) > 1 = v_m(m)$, a contradiction, so $n = m$, and this is the case where $m \geq n$, so we are done.