#P18484. Alternating Paths
Alternating Paths
Alternating Paths
明年,Overly Complicated Problem Colloquium 将在 Greatly Magnificent City 举行。为了给来宾留下深刻印象,城里正在实施多项建设工程,其中包括给所有街道涂色。
这座城市有 个路口和 条连接路口的双向街道,路口编号为 。任意两个路口之间至多有一条街道,没有街道连接同一个路口,而且从任何路口出发都能通过街道走到其他所有路口。
每条街道都要涂成红色或蓝色。市长认为,如果每次经过的街道都与上一条街道颜色不同,在城市里散步会更有趣。因此,他提出了额外要求:对于任意两个不同的路口 ,必须存在一条从 走到 的路线,使相邻两条街道的颜色不同。
这条路线允许多次经过同一个路口,也允许多次经过同一条街道。 第一条街道的颜色没有限制。
请给出满足要求的所有街道的涂色方案,或判断这样的方案不存在。
输入格式
第一行一个整数 (),表示测试用例数量。每个测试用例如下:
第一行两个整数 ,分别表示路口数量和街道数量(,)。接下来 行,每行两个整数 (),表示一条连接路口 的双向街道。保证每个图均无自环、无重边且连通。
每个输入文件中,满足 或 的测试用例至多有 100 个。 这里的条件是“或”。
输出格式
对每个测试用例输出一行。
- 如果不存在符合要求的方案,输出
IMPOSSIBLE。 - 否则输出一个长度为 的字符串,第 个字符为
B表示输入的第 条街道涂蓝色,为R表示涂红色。可以输出任意合法方案。
样例
输入:
3
6 6
1 2
2 3
3 1
4 1
5 2
6 3
6 6
1 2
2 3
3 1
3 4
4 5
4 6
4 3
1 2
4 2
2 3
输出:
RRRBBB
RBBRBB
IMPOSSIBLE
原题为了便于阅读,在样例的测试用例之间额外加入了空行;实际输入不要求这些空行。上面的样例保留了完整的三个用例和全部数据。
下面是前两个用例的一种合法涂色,图片直接取自官方原题:

第三个用例中,无论如何涂色,总会有两个叶子相连的两条街道颜色相同,因此这两个叶子无法通过颜色交替的路线互相到达。