Alternating Road Coloring

In the city of Kitchener, Mayor Alanna has successfully improved the city’s road planning. However, a salesman from the neighboring city RedBlue complains that the road colors are not diverse enough. Alanna’s next task is to paint some of the roads.

The road network of Kitchener is represented by \(N\) intersections and \(M\) roads. The \(i\)-th road connects intersections \(u_i\) and \(v_i\). Initially, all roads are gray. Alanna wishes to color some roads either red or blue such that the following condition holds:

• For every road that remains gray (say connecting intersections \(u_i\) and \(v_i\)), there must exist a path between \(u_i\) and \(v_i\) consisting entirely of painted roads (i.e. roads colored red or blue) in which the colors alternate (red, blue, red, blue, …).

To reduce the city’s expenses, Alanna wants to paint as few roads as possible. Help her design a valid painting scheme. If there are multiple valid schemes, output any one of them.

Note: A path is said to be alternating if consecutive roads along the path have different colors.

inputFormat

The first line of input contains two integers \(N\) and \(M\) \( (1 \leq N, M \leq 10^5)\) representing the number of intersections and the number of roads, respectively.

The next \(M\) lines each contain two integers \(u_i\) and \(v_i\) \( (1 \leq u_i, v_i \leq N)\), indicating that the \(i\)-th road connects intersections \(u_i\) and \(v_i\). The intersections are numbered from 1 to \(N\).

outputFormat

Output a single line containing a string of length \(M\). The \(i\)-th character must be one of the following:

• 'R' if you paint the \(i\)-th road red,
• 'B' if you paint it blue,
• 'G' if you leave it gray.

The output must satisfy the condition that for every road left gray, there is an alternating colored path (using only red and blue roads) connecting its endpoints. Note that if all roads are painted (i.e. no gray road), the condition holds vacuously.

sample

3 3
1 2
2 3
1 3

RRR