Hint 1
Try following the messenger's directions from each entrance one at a time.
Each entrance has a door immediately to the right, but you can eliminate all of the ones that don't lead into a room with a door on the left. Just keep narrowing the choices down one by one.
Be sure to take into account which way the different entrances are facing.

