Let $M,N$ be structures with relation $E$. $E^N$ and $E^M$ are equivalence relations, find sufficient and necessary condition for isomorphism

Question

Let there be signature $S=\{E\}, n_E=2$, and let $M,N$ be S-structures. $E^N$ and $E^M$ are equivalence relations, find a sufficient and necessary condition for $M$ and $N$ being isomorphic.

I conjectured that $|M|=|N|$ at first, but it doesn't seem to work.

Any hints would be of great help!

Answer 1

HINT: For each cardinal $\kappa$ consider the cardinality of the set of $E^N$-equivalence classes of cardinality $\kappa$, and similarly for $E^M$.