you forgot to mention that to solve the puzzle, you must take whatever answer you get from the messengers, and do the opposite.

In other words, the answer you receive is always to take the north road. So you must always negate the answer to get the correct path.