Your contacts are automatically synced to your Live account.
When starting from fresh you log in with this account first, thus getting your contacts back. When you get to the part about restoring there is an option to start afresh.
So all your contacts, non of your apps.