Iranian Mathematical Olympiad

We will prove the statement by induction on $n$. Let $e$ be the last edge, with $i$, $j$ as the labels of its vertices. Deleting $e$ divides the tree into two trees with vertices $I=\{i=i_1,i_2,\dots ,i_k\}$, $J=\{j=j_1,\dots ,j_l\}$ (we denote every vertex by its initial label). By the induction hypothesis, before the last switch the permutation of labels is the product of two cyclic permutations on $I$ and $J$, which after renumbering the indices can be written in the form $$(i_1{i}_2\cdots i_k)(j_1{j}_2\cdots j_l).$$ So the endpoint labels of $e$ before the last operation are $i_2$, $j_2$, and after this operation the permutation of labels becomes $$(i_2{j}_2)(i_1\cdots i_k)(j_1\cdots j_l)=(i_1{j}_2{j}_3\cdots j_l{j}_1{i}_2{i}_3\cdots i_k),$$ which is a cycle of order $n$.