 Solution

Disjoint-cycle decomposition follows by partitioning the set into permutation orbits. Every cycle $(a_1\dots a_r)$ equals $(a_1{a}_r)\cdots (a_1{a}_2)$, so transpositions generate $S_n$; $A_n$ is the kernel of the sign map. For even $m$, an $m$-cycle is odd. Products of pairs of $m$-cycles generate $A_n$ (express the standard generators $(ab)(ac)$ using the hinted overlapping cycles), while adjoining any one $m$-cycle yields all of $S_n$. Thus the set of all $m$-cycles generates $S_n$. For odd $m$, every $m$-cycle is even, so they cannot generate $S_n$.