#P18484. Alternating Paths

Alternating Paths

Alternating Paths

明年,Overly Complicated Problem Colloquium 将在 Greatly Magnificent City 举行。为了给来宾留下深刻印象,城里正在实施多项建设工程,其中包括给所有街道涂色。

这座城市有 nn 个路口和 mm 条连接路口的双向街道,路口编号为 1,2,…,n1,2,\ldots,n。任意两个路口之间至多有一条街道,没有街道连接同一个路口,而且从任何路口出发都能通过街道走到其他所有路口。

每条街道都要涂成红色或蓝色。市长认为,如果每次经过的街道都与上一条街道颜色不同,在城市里散步会更有趣。因此,他提出了额外要求:对于任意两个不同的路口 p,qp,q,必须存在一条从 pp 走到 qq 的路线,使相邻两条街道的颜色不同。

这条路线允许多次经过同一个路口,也允许多次经过同一条街道。 第一条街道的颜色没有限制。

请给出满足要求的所有街道的涂色方案,或判断这样的方案不存在。

输入格式

第一行一个整数 tt(1≤t≤10001\le t\le1000),表示测试用例数量。每个测试用例如下:

第一行两个整数 n,mn,m,分别表示路口数量和街道数量(2≤n≤1002\le n\le100,1≤m≤3001\le m\le300)。接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示一条连接路口 u,vu,v 的双向街道。保证每个图均无自环、无重边且连通。

每个输入文件中,满足 n>50n>50 或 m>150m>150 的测试用例至多有 100 个。 这里的条件是“或”。

输出格式

对每个测试用例输出一行。

  • 如果不存在符合要求的方案,输出 IMPOSSIBLE。
  • 否则输出一个长度为 mm 的字符串,第 ii 个字符为 B 表示输入的第 ii 条街道涂蓝色,为 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

原题为了便于阅读,在样例的测试用例之间额外加入了空行;实际输入不要求这些空行。上面的样例保留了完整的三个用例和全部数据。

下面是前两个用例的一种合法涂色,图片直接取自官方原题:

前两个用例的合法涂色

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