It wasn't the Hagia: it happened on T65, and there was no notice of the Hagia being built anyway. Also, he didn't go Liberty. I later saw that he went full Piety, but I really doubt he finished the tree by T65 even with AI advantages.
I simply can't explain how he got first religion with "Goddess of Protection" faster than any other Piety-taking Civ, even though they did take Faith pantheons.