Answer: $(x,y,p,m,n)=( 1 ,1 ,2 ,1 ,1)$ $(x,y,p,m,n) =(2 ,5 ,3 ,3, 2)$ $(x,y,p,m,n) =(5, 2, 3 ,2 ,3)$ Progress: When $m=n$, we have $x^2+y=x+y^2 \implies x=y$ So $x(x+1)=p^m \implies x =y=m=n=1, p = 2$ I think we can show p <5 by mod 6. But it's a lot of work.

Notice that if $m = n$, then we must have $x = y$. This gives us $(x,y,m,n) = (1,1,1,1)$ and $p = 2$. WLOG $m < n$, then we have $y < x$. So, $x + y^2 | x^2 + y$. Notice that $(x,y) = 1$. Thus, we have \[ x + y^2 | y^3 + 1 \]Suppose $x + y^2 = p^n$ where $p \not= 3$, or $p = 3$ but $(y + 1, y^2 - y + 1) = 1$. \[ x + y^2 | y + 1 \]\[ x + y^2 | y^2 - y + 1\]Which are both impossible for size reasons. Then, we just need to consider when $p = 3$. \[ x + y^2 | 3(y^2 - y + 1) \]Then, we have $3^{n - 1}| y^2 - y + 1$. So $y^2 - y + 1 = k . 3^{n - 1}$. Suppose $k \ge 3$, then we have $y^2 - y + 1 \ge 3^n = x + y^2$, which is impossible So $k = 1$ or $k = 2$. If $y^2 - y + 1 = 2 . 3^{n - 1}$, LHS must be odd while RHS is even. So, $y^2 - y + 1 = 3^{n - 1}$. Then we have $y^3 + 1 = 3^{n - 1} . (y + 1)$. Checking $y = 1$, we have $n = 1$. Then, $x = 2$, but $y + x^2 = 5 \not= 3^m$. A contradiction. Checking $y = 2$, we have $n = 2$. Then, $x = 5$, then $y + x^2 = 27 = 3^3$, which is a solution. If $y \ge 3$, notice that by Zsigmondy Theorem, there exists a primitive prime divisor of $y^3 + 1$ which is not in $y + 1$, and furthermore, notice that $3 | y + 1$. So, we are hence finished. So, we have three solutions : $(x,y,m,n,p) = (1,1,1,1,2), (2,5,2,3,3), (5,2,3,2,3)$

WLOG assume $x\ge y$, we will divide this into two cases. Case 1.$\quad x=y$ We have, $$x(x+1)=p^m=p^n$$Because $gcd(x,x+1)=1$ we must have $m=n=1$. It follows that the only solution is $(x,y,p,m,n)=(1,1,2,1,1)$. Case 2.$\quad x>y$ Assume $gcd(x,y) \ne1$, let $gcd(x,y)=p^k$ with $k,a,b\in \mathbb{N}$ such that $x=p^ka$ and $y=p^kb$. We have, $$a+p^kb^2=p^{m-k}$$$$p^ka^2+b=p^{n-k}$$Because $m,n>k$, we must have $p|a$ and $p|b$ from those two equation. A contradiction, therefore $gcd(x,y)=1$. Notice that, $$(x+y-1)(x-y)>0 \Rightarrow x^2+y>x+y^2 \Rightarrow p^n>p^m$$Hence $p^m|p^n$, which is equivalent to $$x+y^2|x^2+y \Rightarrow x^2+y|y^4+y \Rightarrow p^m|(y+1)(y^2-y+1) \quad (1)$$Notice that $gcd(y+1,y^2-y+1)=1$ or $3$, if $gcd(y+1,y^2-y+1)=1$. Then $$p^m|y+1 \Rightarrow x+y^2\le y+1$$or $$p^m|y^2-y+1 \Rightarrow x+y^2\le y^2-y+1$$Both possibility implies a contradiction(size reason), then we must have $gcd(y+1,y^2-y+1)=3$. Therefore $p=3$, from $(1)$ $$3^{m-2}|\big(\frac{y+1}{3}\big)\big(\frac{y^2-y+1}{3}\big)$$Because $gcd\big(\frac{y+1}{3},\frac{y^2-y+1}{3}\big)=1$, $$3^{m-2}|\frac{y+1}{3} \Rightarrow 3^{m-1}|y+1$$or $$3^{m-2}|\frac{y^2-y+1}{3} \Rightarrow 3^{m-1}|y^2-y+1$$By size reason, of course $3^{m-1}|y^2-y+1$. Notice that $y^2-y+1$ is odd, because $y^2-y+1<x+y^2=3^m$, $y^2-y+1=3^{n-1}$. We have $y^3+1=3^{n-1}(y+1)$. For $y\le 2$, the only solution is $(x,y,p,m,n)=(5,2,3,2,3)$ For $y\ge3$, notice that $3|y+1$. By Zsigmondy, there exist a prime $p$ such that $p|y^3+1$ and $p\nmid y+1$ which implies $p|3^{n-1}(y+1)$. A contradiction, the only solution for this case is $(x,y,p,m,n)=(5,2,3,2,3)$. We can conclude from those two cases, that the only solutions are $(x,y,p,m,n)=(1,1,2,1,1),(5,2,3,2,3),(2,5,3,3,2)$.

IndoMathXdZ wrote: WLOG $m < n$, then we have $y < x$. So, $x + y^2 | x^2 + y$. Notice that $(x,y) = 1$. I'm sorry, but why must we immediately have $(x,y)=1$? EDIT, ok I saw in below posts, but yeah, this just needs a bit of justification.

Here's a very quick simple approach. Answer. $(1,1)$, $(2,5)$, $(5,2)$ Let $a^2 + b = p^m$, $a + b^2 = p^n$, without loss of generailty let $m\leq n$. If $m=n$, and $a^2 + b = a + b^2$, so $(a-b)(a+b-1) = 0$ and $a=b$, but in $a(a+1) = p^m$ the multipliers on the left are coprime, whence $a=1$ (and $a=b=1$ satisfies the requirements). From now on $m < n$, so (as above) $a<b$. Then $a^2 + b = p^m$ divides $b^2 + a = p^n$, thus $a^2 + b$ also divides $a^4 + a$ (as $a^4 - b^2 = (a^2-b)(a^2+b)$ is divisible by $a^2+b$), i.e. \[ p^m = a^2 + b \mbox{ divides } a(a+1)(a^2-a+1).\]We have $\gcd(a,a+1) = $ $\gcd(a, a^2 - a + 1) = 1$ and $\gcd(a+1, a^2-a+1) = 1$ or $3$. Hence if $a$ is divisible by $p$, then $p^m$ is coprime with $a+1$ and $a^2-a+1$ and necessarily divides $a$, implying $a^2 + b = p^m \leq a$, impossible. From now on we assume that $a$ is not divisible by $p$ and hence $p^m$ divides $(a+1)(a^2 - a + 1)$. We have two cases: If $p\neq 3$, then $p^m = a^2 + b$ divides fully at least one of $a+1$ and $a^2-a+1$ (due to their gcd), which is impossible for $a\geq 2$, as $a^2 + b > a^2 \geq a^2 - a + 1 \geq a + 1$; and for $a=1$ we need $p^m$ to divide $2$, so $p=2$, $m=1$ and $b=1$, which we got in the beginning. Now let $p=3$. Necessarily $a+1$ and $a^2-a+1$ are divisible by $3$ (and $m\geq 2$), otherwise they are coprime and we obtain a contradiction as in the previous case. Direct verification shows that $a^2-a+1$ is not divisible by $9$ for any $a$. Hence in \[ \frac{a^2+b}{9} = 3^{m-2} \mbox{ divides } \frac{a+1}{3} \cdot \frac{a^2-a+1}{3} \]the dividend and the multiplier $\displaystyle \frac{a^2-a+1}{3}$ are coprime, so necessarily $\displaystyle \frac{a^2+b}{9}$ divides $\displaystyle \frac{a+1}{3}$. In particular, $a^2 + a + 1 \leq a^2 + b \leq 3a + 3$, i.e. $a(a-2) \leq 2$. Therefore (as $a+1$ is divisible by $3$) the only option is $a=2$ and $\displaystyle \frac{4+b}{9}$ to divide $1$, i.e. $b=5$. Note that $(2,5)$ (and $(5,2)$) is indeed a solution, since $2^2 + 5 = 3^2$ and $5^2 + 2 = 3^3$.