P10298 [CCC 2024 S4] Painting Roads

The mayor of Kitchener, Alanna, has successfully improved the city’s road plan. However, a salesperson from RedBlue City still complains that the roads are not colorful enough. Alanna’s next task is to paint some roads. Kitchener’s road plan can be represented as $N$ intersections and $M$ roads. Road $i$ connects intersection $u_i$ and intersection $v_i$. At the beginning, all roads are gray. Alanna wants to paint some roads red or blue such that: - For every gray road, suppose it connects intersections $u_i$ and $v_i$. There must exist a path from intersection $u_i$ to intersection $v_i$ such that the road colors along the path alternate between red and blue, and no road on the path is gray. To reduce the city’s spending, Alanna wants to paint as few roads as possible. Please help Alanna design a painting plan that satisfies the requirement.

The first line contains two integers $N$ and $M$ ($1 \leq N, M \leq 2 \times 10^5$). Each of the next $M$ lines contains two integers $u_i$ and $v_i$, indicating that there is a road connecting intersections $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$, $u_i \neq v_i$). Between any two intersections, there is at most one road.

Output a string of length $M$ describing the painting plan. The $i$-th character represents the color of road $i$: `R` means red, `B` means blue, and `G` means gray (unpainted). Note that you must minimize the number of painted roads while satisfying the condition. If there are multiple such painting plans, output any one of them.

**[Sample 1 Explanation]** A diagram of the intersections and the valid roads is shown below. This plan minimizes the number of painted roads. Note that each road is labeled with R (red), B (blue), or G (gray).  All unpainted roads satisfy the condition: - The second road, labeled $G_2$, connects intersections $2$ and $4$. On the path $2, 1, 4$, the roads are painted red, blue. - The third road, labeled $G_3$, connects intersections $5$ and $2$. On the path $5, 4, 1, 2$, the roads are painted red, blue, red. - The fifth road, labeled $G_5$, connects intersections $4$ and $3$. On the path $4, 1, 3$, the roads are painted blue, red. **[Sample 2 Explanation]** Note that Kitchener’s road graph may be disconnected. **[Constraints]** **This problem uses bundled testdata.** For all testdata, it is guaranteed that $1 \leq N, M \leq 2 \times 10^5$, $1 \leq u_i, v_i \leq N$, and $u_i \neq v_i$. The table below shows the distribution of the $15$ points: | Points | Additional Condition | | :-: | :- | | $2$ | For every $1 \leq i < N$, there is a road connecting $i$ and $i + 1$ (there may also be other roads). | | $3$ | The graph is connected and $N = M$. | | $3$ | No road belongs to at least two simple cycles at the same time (see the definition below). | | $7$ | None. | Definition: Using $u \leftrightarrow v$ to represent a road connecting $u$ and $v$, for $k \geq 3$ and all $w_i$ pairwise distinct, the sequence $w_1 \leftrightarrow w_2 \leftrightarrow \cdots \leftrightarrow w_k \leftrightarrow w_1$ is called a simple cycle. Translated by ChatGPT 5