Subgroup of $S_n$ generated by $(1,2,\cdots,n)$ and $(1,2,\cdots,m)$.

I'll be using right actions (so for $x,y\in S_n$, $xy$ means apply $x$ then $y$) and the notation $x^y=y^{-1}xy$.

I will assume the following (which can be proved by induction):

$A_n=\langle(1,2,3),(2,3,4),\ldots,(n-2,n-1,n)\rangle$

Let $\sigma=(1,\ldots,n)$, $\tau=(1,\ldots,m)$, so

$$\tau^\sigma=(2,3,\ldots,m+1)$$ $$\tau(\tau^\sigma)^{-1}=(1,m+1,m)$$ $$\left(\tau(\tau^\sigma)^{-1}\right)^{(\tau^\sigma)^2}=(1,3,2)$$

So $(1,3,2)\in G$ and therefore $(1,2,3)\in G$.

For $i=1,\ldots,n-3$ we have $(1,2,3)^{\sigma^i}=(i+1,i+2,i+3)$ giving $A_n\le G$.

Clearly $G=A_n$ if and only if $\sigma,\tau\in A_n$ if and only if $n$ and $m$ are odd.

It is enough to show that $G$ contains enough $3$-cycles to generate $A_n$.

Note that $(m+1,2,\ldots,m)=(1,\ldots,n)(1,\ldots,m)(1,\ldots,n)^{-1} \in G$.

So $(1,2,m+1) = (1,2,\ldots,m)(m+1,2,\ldots,m)^{-1} \in G$.

So $(1,2,3) = (m+1,2,\ldots,m)(1,2,m+1)^{-1}(m+1,2,\ldots,m)^{-1} \in G$.

By conjugating $G$ contains every $(k,k+1,k+2)$.

Thus $G$ contains permutations $\sigma$ such that $\sigma(1)=1$, $\sigma(2)=2$ and $\sigma(3)$ is arbitrary.

By considering the $\sigma (1,2,3) \sigma^{-1}$, $\sigma \in G$, it follows that $G$ contains all of the $(1,2,j)$, $j \geq 3$.

For $i \neq j$, $i,j > 2$, $(1,j,i)=(1,2,i)(1,2,j)^{-1} \in G$. So $G$ contains all of the $(1,i,j)$.

So for distinct $i,j,k$, $(i,j,k)=(1,i,j)(1,j,k) \in G$. As a conclusion, $G \supset A_n$.