Since there are no edges between the cliques $E_1$ and $E_2$ we know that every connected component of $S$ must entirely lie in one of these cliques. To exploit this property, it is convenient to view the graphs $E$ as $0/1$ colorings of vertices. Namely, every coloring $h:[m]\to\{0,1\}$ of vertices defines the graph $E_h=\Big\{\{u,v\}\colon h(u)=h(v)\Big\}$, a union of two disjoint cliques, as before. There are $2^{m-1}$ non-constant colorings $h$. The colorings $h(x)$ and $1-h(x)$ define the same graph, but we will consider them as different for counting purposes.
Fix a set $S$ of $|S|=s+1$ edges, and let $v$ be the number of vertices touched by $S$. Let $F$ be a spanning forest of $S$ with the maximum number $|F|$ of edges, $T_1,\ldots,T_d$ be the trees of $F$, and $v_1,\ldots,v_d$ be the numbers of vertices in these trees (note that $v_i\geq 2$ for each $i$). Since $|T_i|=v_i-1$, we have $|F|=v-d\geq \sqrt{s+1}$, where the inequality follows from: \[ (v-d)^2=|F|^2=[(v_1-1)+\cdots+(v_d-1)]^2 \geq \sum_{i=1}^d(v_i-1)^2 \geq \sum_{i=1}^d \binom{v_i}{2}\geq |S|=s+1 \] All vertices of each of the $d$ trees $T_i$ must receive the same color. So, the number of ways to assign one of the colors 0 and 1 to each of the $d$ trees is $2^d$, and the number of ways to color the remaining $m-v$ vertices is at most $2^{m-v}$. So, the number of colorings $h$ with $E_h\supseteq S$ is at most \[ 2^d\cdot 2^{m-v} = 2^{m-(v-d)} \leq 2^{m-\sqrt{s}}. \] Since we have $2^{m-1}$ colorings, by taking $s=\lfloor 10\log^2m \rfloor$ the desired lower bound \[ t\geq \frac{2^{m-1}}{2^{m-\sqrt{s}}}=2^{\sqrt{s}-1}\geq m^3 \] follows. $\Box$