Two-Sided Matching with (Almost) One-Sided Preferences