For any cycle decomposition, we can uniquely order the cycles from smallest length to largest length, breaking ties between cycles of the same length in some fixed arbitrary way (say by maximal elements). Let us do this for concreteness.

Suppose there was an (injective) way to "join" and A-cycle and a B-cycle together to form an A+B cycle whenever |A| and |B| are > 1. Then, given any cycle decomposition as above, one can start bubbling the two largest cycles together to eventually form a single cycle of some length m.

If m = n - 1, we are done.

If m = n, write S = (1............) and then omit the last term.

If m = 1 the problem is very easy.

If n - 1 > m > 2, there is an injective map from m-cycles to elements whose cycle decomposition is a product of an m-cycle with a 2-cycle. For concreteness, one can add the 2-cycle with the two lowest missing entries. Now bubble again to form an m+2 cycle.

If m = 2, and n is at least 5, bubble with a 3-cycle.

If m = 2 and n = 4 (the last case), form whatever bijection you like between the two sets of 6 elements.

The key point is therefore to find a way to bubble an A-cycle and a B-cycle when |A|,|B| > 1.
We do this as follows.

Amongst the entries of A and B, there is a unique smallest integer, call it X.

Case 1. If X lies in A, Let Z denote the *largest* element of B.
Then one can (uniquely) write A = (X.....) and B = (.....Y,Z), where Y < Z. Then consider the A+B cycle obtained by concatenating A and B in this form, i.e. (X,......,Y,
Z).

Case 2. If X lies in B, let Z denote the *smallest* element of A.
Then one can (uniquely) write B = (X....) and A = (.....,Y,Z), where now Y > Z.
Then consider the A+B cycle (X,.....,Y,Z).

Given an A+B cycle, one can uniquely write it in the form (X,....,Y,Z), where X is the smallest entry. Then one can break it up into an A-cycle and B-cycle depending on whether Y < Z or Y > Z.

Since this was apparently a little confusing, suppose that the cycle lengths of S are
a`_`

1 <= a`_`

2 <= a`_`

3 <= ..... <= a`_`

r.
Here I omit the 1-cycle lengths, so a`_`

1 > 1, and sum a`_`

r = m for some m possibly less than n. Then the cycle lengths of the steps in the algorithm will have lengths:

(a`_`

1, ...., a`_`

(r-1),a`_`

r),

(a`_`

1, ...., a`_`

(r-2),a`_`

(r-1) + a`_`

r),

(a`_`

1, ...., a`_`

(r-3),a`_`

(r-2) + a`_`

(r-1) + a`_`

r),

....

(a`_`

1 + a`_`

_2 + ... + a`_`

r) = (m)

(2,m)

(m+2)

(2,m+2)

(m+4)

...

(n-1 or n, depending on m mod 2),

then n-1.

(if m = 2 and n is at least 5, then instead it should go

(2) --> (2,3) --> (5) --> (2,5) --> (7) --> (2,7) --> (9) ...,etc.