Lesson 4

Programming problem. Write a program that receives as input a graph with a 3-coloring of its vertices and changes the color of each vertex so that the resulting coloring is proper.

The first line contains the number of vertices \(1 \le n \le 1\ 000\) and the number of edges \(0 \le m \le 20\ 000\). The next line contains the 3-coloring of the vertices \(\{\texttt{R}, \texttt{G}, \texttt{B}\}^{n}\). Each of the next \(m\) lines specifies an edge of the graph.

Output a proper 3-coloring where each vertex is assigned a color different from its input color, in the same format. If no such 3-coloring exists, output \(\texttt{Impossible}\).

4 5
RRRG
1 3
1 4
3 4
2 4
2 3

GGBR