{"problem":{"name":"[CCC 2024 S4] Painting Roads","description":{"content":"Kitchener 市的市长 Alanna 成功地改进了该市的道路规划。然而，来自 RedBlue 市的一位售货员仍然抱怨道路的颜色不够丰富。Alanna 的下一个任务就是粉刷一些道路。 Kitchener 市的道路规划可以表示为 $N$ 个十字路口和 $M$ 条道路，第 $i$ 条道路连接第 $u_i$ 个十字路口和第 $v_i$ 个十字路口。一开始所有道路都是灰色的。Alanna 想要把一些","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10298"},"statements":[{"statement_type":"Markdown","content":"Kitchener 市的市长 Alanna 成功地改进了该市的道路规划。然而，来自 RedBlue 市的一位售货员仍然抱怨道路的颜色不够丰富。Alanna 的下一个任务就是粉刷一些道路。\n\nKitchener 市的道路规划可以表示为 $N$ 个十字路口和 $M$ 条道路，第 $i$ 条道路连接第 $u_i$ 个十字路口和第 $v_i$ 个十字路口。一开始所有道路都是灰色的。Alanna 想要把一些道路染成红色或者蓝色，满足以下条件：\n\n- 对于每一条灰色道路，假设其连接十字路口 $u_i$ 和十字路口 $v_i$，一定存在一条从十字路口 $u_i$ 到十字路口 $v_i$ 的路径，满足路径上的道路颜色红色和蓝色交替出现，任何道路都不是灰色的。\n\n为了降低城市的支出，Alanna 希望尽可能少地对道路进行染色。请帮助 Alanna 设计一个符合要求的染色方案。\n\n## Input\n\n输入的第一行包含两个整数 $N$ 和 $M$（$1\\leq N, M \\leq 2 \\times 10^5$）。\n\n接下来 $M$ 行中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ 表示存在一条连接十字路口 $u_i$ 和十字路口 $v_i$ 的道路（$1 \\leq u_i, v_i \\leq N$，$u_i \\neq v_i$）。\n\n任意两个十字路口之间至多存在一条道路。\n\n## Output\n\n输出一个长度为 $M$ 的字符串，表示染色的方案。第 $i$ 个字符表示第 $i$ 条道路的颜色，`R` 表示红色，`B` 表示蓝色，`G` 表示灰色（未染色）。\n\n注意你必须在满足条件的情况下最小化染色的道路数目。如果存在多个这样的染色方案，输出任意一个。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n十字路口以及有效的道路的示意图如下所示，该方案最小化了染色道路的数量。请注意，每条道路上的颜色显示为 R（红色）、B（蓝色）或 G（灰色）。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/vwughkb3.png)\n\n所有为染色的道路都满足条件：\n\n- 第二条路标记为 $G_2$ 连接了十字路口 $2$ 和 $4$，路径 $2, 1, 4$ 上的道路被染上红色、蓝色。\n- 第三条路标记为 $G_3$ 连接了十字路口 $5$ 和 $2$，路径 $5, 4, 1, 2$ 上的道路被染上红色、蓝色、红色。\n- 第五条路标记为 $G_5$ 连接了十字路口 $4$ 和 $3$，路径 $4, 1, 3$ 上的道路被染上蓝色、红色。\n\n**【样例 2 解释】**\n\n请注意 Kitchener 的道路可能不是连通的。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n对于所有数据，保证 $1\\leq N, M \\leq 2 \\times 10^5$，$1 \\leq u_i, v_i \\leq N$，$u_i \\neq v_i$。\n\n下面的表格显示了 $15$ 分的分配方案：\n\n| 分值 | 附加条件 |\n| :-: | :- |\n| $2$ | 对任意 $1 \\leq i < N$ 存在一条连接 $i$ 和 $i + 1$ 的道路（还可能存在其他道路） |\n| $3$ | 图连通并且 $N = M$ |\n| $3$ | 任何道路都不同时属于至少两个简单环（见下文定义） |\n| $7$ | 无 |\n\n定义：若用 $u \\leftrightarrow v$ 表示一条连接 $u$ 和 $v$ 的道路，则称 $k \\geq 3$ 且所有 $w_i$ 互不相同是序列 $w_1 \\leftrightarrow w_2 \\leftrightarrow \\cdots \\leftrightarrow w_k \\leftrightarrow w_1$ 为简单环。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10298","tags":["图论","2024","Special Judge","CCC（加拿大）","生成树","构造"],"sample_group":[["5 7\n1 2\n2 4\n5 2\n4 5\n4 3\n1 3\n1 4\n","BRGBBGG\n"],["4 2\n1 2\n3 4\n","BB\n"]],"created_at":"2026-03-03 11:09:25"}}