Complement Spanning Trees

You are given a small graph $G_s$ with $N$ nodes (numbered $1$ through $N$) and $M$ edges. Let's create a big graph $G_b$ with $NK$ nodes (numbered $1$ through $NK$) and $MK$ edges. $G_b$ consists of $K$ copies of $G_s$ ― formally, for each $k$ ($0 \le k \le K-1$) and each edge between nodes $u$ and $v$ in $G_s$, there is an edge between nodes $u+kN$ and $v+kN$ in $G_b$. Afterwards, let's take t