32367번 - Painting Roads 서브태스크스페셜 저지다국어

문제

Alanna, the mayor of Kitchener, has successfully improved the city’s road plan. However, a traveling salesperson from the city of RedBlue complained that the roads are not colourful enough. Alanna’s second job is to paint some of the roads.

Kitchener’s road plan can be represented as a collection of N intersections with M roads, where the i-th road connects intersections u_i and v_i. All roads are initially grey. Alanna would like to paint some of the roads in red or blue such that the following condition is satisfied:

• Whenever there is a grey road that connects u_i and v_i, there is also a path of roads from u_i to v_i such that the roads on the path alternate between red and blue, without any of the roads on this path being grey.

To lower the city’s annual spending, Alanna would like to minimize the number of painted roads. Can you help Alanna design a plan that meets all the requirements?

입력

The first line contains two integers N and M (1 ≤ N, M ≤ 2 · 10⁵).

The i-th of the next M lines contains two integers u_i and v_i, meaning that there exists a road from intersection u_i to intersection v_i (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i).

There is at most one road between any unordered pair of intersections.

출력

Output a string of M characters, representing the paint plan. The i-th character should be R if the i-th road is to be painted red, B if i-th road is to be painted blue, or G (for “grey”) if the i-th road is to be left unpainted.

Remember that you must minimize the number of painted roads while satisfying the condition. If there are multiple possible such plans, output any of them.

제한

서브태스크

Definition: if we denote a road between intersections u and v as u ↔ v, then a simple cycle is a sequence w₁ ↔ w₂ ↔ . . . ↔ w_k ↔ w₁ where k ≥ 3 and all w_i are distinct.

힌트