Hence the total number of branches is at most $2^8$. We discard any branch that yields a $1$-edge or $2$-cycle. Let $S_1' = S_1 \setminus Z$ and $T_1'=T_1 \setminus Z$. For each remaining branch we try to colour the remaining vertices of $G$, which are all in $S_1'\cup T_1'\cup \{u\}$, and keep track of any minimum $1$-set found. In the end we return a $1$-set of minimum size (recall that $G$ has at least two $1$-sets).

For any remaining branch we do as follows. We first give colour $1$ to $u$. Then every vertex of $S_1'\cup T_1'$ must get colour $2$. If this does not yield a $1$-edge or $2$-cycle, we obtain a $1$-set, which we remember if it is the smallest one found so far.

We now give colour $2$ to $u$. If $u$ was the only remaining vertex, we check for the presence of a $1$-edge or a $2$-cycle, and if none is present, we remember the $1$-set found if it is the smallest one found so far. Otherwise, we let $D_1,\ldots,D_r$ for some integer $r\geq 1$ be the connected components of the (bipartite) graph induced by $S_1'\cup T_1'$. As these vertices do not belong to $Z$, each 