The strategy is to prove both directions: conjugation preserves cycle type (forward), and any two permutations of the same cycle type can be explicitly conjugated into each other (backward). **Step 1: Conjugation preserves cycle type (forward).** Let $\sigma \in S_n$ have cycle decomposition $\sigma = (a_{11}\; \ldots\; a_{1n_1})(a_{21}\; \ldots\; a_{2n_2}) \cdots (a_{k1}\; \ldots\; a_{kn_k})$. For any $\tau \in S_n$, we compute $\tau\sigma\tau^{-1}$ by tracking where it sends $\tau(a_{ij})$: \begin{align*} \tau\sigma\tau^{-1}(\tau(a_{ij})) = \tau(\sigma(a_{ij})) = \begin{cases} \tau(a_{ij+1}) & \text{if } j < n_i, \\ \tau(a_{i1}) & \text{if } j = n_i. \end{cases} \end{align*} So $\tau\sigma\tau^{-1} = (\tau(a_{11})\; \ldots\; \tau(a_{1n_1}))(\tau(a_{21})\; \ldots\; \tau(a_{2n_2})) \cdots (\tau(a_{k1})\; \ldots\; \tau(a_{kn_k}))$, which has the same cycle type $(n_1, n_2, \ldots, n_k)$ as $\sigma$. **Step 2: Same cycle type implies conjugate (backward).** Suppose $\pi$ has the same cycle type as $\sigma$. Write: \begin{align*} \sigma &= (a_{11}\; \ldots\; a_{1n_1}) \cdots (a_{k1}\; \ldots\; a_{kn_k}), \\ \pi &= (b_{11}\; \ldots\; b_{1n_1}) \cdots (b_{k1}\; \ldots\; b_{kn_k}). \end{align*} Define $\tau \in S_n$ by $\tau(a_{ij}) = b_{ij}$ for all $i, j$. This is well-defined and bijective since both decompositions list each element of $\{1, \ldots, n\}$ exactly once. By Step 1, $\tau\sigma\tau^{-1} = \pi$.