Restoring deleted contacts

I deleted my contacts off of one phone, and it deleted the same contacts synced to another phone that someone else is using. We used to have the same apple ID but we changed the other phones apple ID and the contacts still deleted. I tried iCloud backup. I tried using iCloud.com and restoring but nothing is working.