I did a simulation. There was a glitch on one output if the relays close faster than they open -- which is often the case, particularly with DC relays snubbed with diodes.
The minor modification fixes that without requiring any more relays. Relay count now is:
2 DPDT 1 SPSTIf your relay coils aren't the same voltage as your load, then you may need to add a couple of SPST load relays.
This was fun. I haven't designed relay logic for decades!