Proving cardinality given surjection from A to B and B to A

Suppose f:A→B and g:B→A are both surjective, does this imply that there is a bijection between A and B.

I was told that the statement above is true only with Axiom of Choice. Can someone provide an example of why that is the case?