No need to replace anything before proper diagnose of the issue once i drove my rebirth in deep water the water was till headlights when car came out from water this message showed on imid i remove battery terminals for one night then installed them back issue got resolved
But in your case i think its faulty o2 sensor or chocked catalytic converter
In my case car was not changing gears along with this msg