Here is the complete algorithm:
Read , . Build adjacency list from edges.
Create color array of size , all .
For each pupil from to : if color[i] == -1, run BFS, coloring with and . If conflict found, print "IMPOSSIBLE" and exit.
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 time and uses space.