CSES 1668 Building Teams - Algorithm

Here is the complete algorithm:

$1.$ Read $n$, $m$. Build adjacency list from $m$ edges.

$2.$ Create color array of size $n+1$, all $-1$.

$3.$ For each pupil $i$ from $1$ to $n$: if color[i] == -1, run BFS, coloring with $0$ and $1$. If conflict found, print "IMPOSSIBLE" and exit.

$4.$ If no conflicts, print color[1]+1, color[2]+1, ..., color[n]+1. That is it. The algorithm you already know produces the output directly. This runs in $O(V + E)$ time and uses $O(V)$ space.