Ok, i can not draw a diagram at the moment but basically, i am using TRACO POWER 1-2450 5V power supply for each. Wallwart (9V) connects to all 3 of them. So one 1-2450 for relay, one for MEGA and one for UNO. After a lot of testing and having each of them have its own power supply i was able to greatly reduce interference and noise from MAX7219 chips on other components and sensors.
I can not find that relay online any more, got it long time ago but something like this:
and power supply: