This is a funny linear algebra problem in $\mathbb{F}_2$. Interpret each operation as a vector in $\mathbb{F}_2$ that affects the $m$ edges. Therefore, from each configuration of edges, I can reach $2^n$ total configurations. There are $m$ edges so there are $2^m$ ways to color the edges. There are at most $2^n$ ways to reach from starting config all red, and at most $2^n$ ways to go from starting config all blue edges. If we toggle every vertex, each edge gets toggled twice so we start at the original configuration. Thus, there are actually at most $2^{n-1}$ configurations that I can go from any starting configuration.

Just a small note. There are two configuration with all the edges colored in the same color, Reaching either of them is banned. So, if you reach at most $2^{n-1}$ configurations, this number must be multiplied by 2 if you want to count the reachable configurations + their flipping counterparts. Fortunately $2.2^{n-1}=2^n<2^m$ all russian regional 1993

Another remark: The problem is false when $m=n$. If $n$ is odd, consider $C_n$.