I just realized: the story those two guests said happened between the Queen and the Hero was actually what the priest/gods saw in their prophecy in the beginning. Technically speaking, she would be freed from the doomed future by simply changing into a different identity at this point.