Red Blue Graph

Arghya BUET Inter University Pro...
Limits 4s, 512 MB

You are given a connected, undirected, unweighted graph. You need to assign one of the two colors Red or Blue to every edge of the graph in such a way that, for each node degreeRdegreeB1|degree_R-degree_B| \leq 1.
degreeRdegree_R of a node is the number of adjacent edges to that node which are colored Red.
degreeBdegree_B of a node is the number of adjacent edges to that node which are colored Blue.

                                    

Input

The first line contains one integer TT - the number of test cases. First line of each testcase contains two integers NN, MM - the number of vertices and the number of edges in the graph respectively. Each of the next MM lines contain two integers uiu_i and viv_i describing an undirected edge in the graph.

1T1001 \leq T \leq 100
1N1051 \leq N \leq 10^5
N1Mmin(3105,(N(N1))/2)N-1 \leq M \leq min(3*10^5, (N*(N-1))/2)
Sum of NN over all testcases doesn’t exceed 10610^6 and sum of MM over all testcases also doesn’t exceed 10610^6.
It is guaranteed that the graph is connected, it has no self-loop and there is at most one edge between every pair of vertices.

Output

If it is not possible to find such a coloring, print 1-1. Otherwise print one such coloring of the edges in the order given. If there exists more than one coloring you can print any one. You should print a string containing only RR and BB to denote the coloring.

Sample

InputOutput
2
6 5
1 2
1 3
2 4
2 5
5 6
3 3
1 2
2 3
1 3
BRRRB
-1

Submit

Login to submit.

Statistics

67% Solution Ratio
MrBrionixEarliest, 3M ago
Sk_SabitFastest, 0.2s
Sk_SabitLightest, 20 MB
MrBrionixShortest, 2748B
Toph uses cookies. By continuing you agree to our Cookie Policy.