Problem Description

Mayor Alanna of Kitchener City has successfully improved the city's road planning. However, a salesman from RedBlue City still complains that the roads are not colorful enough. Alanna's next task is to paint some roads.

The road planning of Kitchener City can be represented as $N$ intersections and $M$ roads, where the $i$-th road connects the $u_i$-th intersection and the $v_i$-th intersection. Initially, all roads are gray. Alanna wants to paint some roads red or blue, subject to the following conditions:

• For every gray road connecting intersections $u_i$ and $v_i$, there must exist a path from intersection $u_i$ to intersection $v_i$ where the road colors alternate between red and blue, and no road is gray.

To reduce city expenses, Alanna wants to paint as few roads as possible. Help Alanna design a painting scheme that meets the requirements.

Input Format

The first line of input contains two integers $N$ and $M$ ($1 \leq N, M \leq 2 \times 10^5$).

The next $M$ lines contain two integers $u_i$ and $v_i$ each, indicating that there is a road connecting intersection $u_i$ and intersection $v_i$ ($1 \leq u_i, v_i \leq N$, $u_i \neq v_i$).

There is at most one road between any two intersections.

Output Format

Output a string of length $M$ representing the painting scheme. The $i$-th character represents the color of the $i$-th road, where R stands for red, B stands for blue, and G stands for gray (unpainted).

Note that you must minimize the number of painted roads while satisfying the conditions. If there are multiple such painting schemes, output any one.

Sample Input and Output

Sample Input #1

5 7
1 2
2 4
5 2
4 5
4 3
1 3
1 4

Sample Output #1

BRGBBGG

Sample Input #2

4 2
1 2
3 4

Sample Output #2

BB

Notes/Hints

[Sample 1 Explanation]

The diagram of intersections and valid roads is shown below, which minimizes the number of painted roads. Note that the colors on each road are indicated as R (red), B (blue), or G (gray).

All unpainted roads meet the conditions:

• The second road marked as $G_2$ connects intersections $2$ and $4$, with the path $2, 1, 4$ painted red, blue.
• The third road marked as $G_3$ connects intersections $5$ and $2$, with the path $5, 4, 1, 2$ painted red, blue, red.
• The fifth road marked as $G_5$ connects intersections $4$ and $3$, with the path $4, 1, 3$ painted blue, red.

[Sample 2 Explanation]

Note that the roads in Kitchener may not be connected.

[Data Range]

This problem is group testing.

For all data, it is guaranteed that $1 \leq N, M \leq 2 \times 10^5$, $1 \leq u_i, v_i \leq N$, $u_i \neq v_i$.

The following table shows the allocation of $15$ points:

Definition: If $u \leftrightarrow v$ denotes a road connecting $u$ and $v$, then a sequence $w_1 \leftrightarrow w_2 \leftrightarrow \cdots \leftrightarrow w_k \leftrightarrow w_1$ with $k \geq 3$ and all $w_i$ distinct is called a simple cycle.

见题面 Input 部分

见题面 Output 部分