One note on the OP is that the NRMP doesn't use Gale-Shapley, it actually uses the Roth-Peranson algorithm which is a slight modification of the original Gale-Shapley one.