CSES - Graph painting
  • Time limit: 1.00 s
  • Memory limit: 256 MB

You are given a simple, undirected graph that consists of nn nodes and mm edges.

Your task is to paint each node red or blue so that there are at least m/2\lfloor m/2 \rfloor edges such that their nodes have a different color.

Input

The first input line contains an integer tt: the number of test cases. After this, there are tt test cases that are described as follows:

The first line contains two integers nn and mm: the number of nodes and edges in the graph. The nodes are numbered 1,2,,n1,2,\ldots,n.

After this, there are mm lines that describe the edges. Each line contains two integers aa and bb. This means that there is an edge between nodes aa and bb.

Output

For each test case, output a line that contains nn space separated characters that describe the colors of the nodes. Each character must be R (red) or B (blue).

There is always a solution, and you can output any valid solution.

Constraints

  • 1t1001 \le t \le 100
  • 2n1052 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • the sum of all nn and mm values it at most 10610^6

Example

Input:

3
2 1
1 2
4 4
1 2
2 3
3 4
1 4
5 3
1 2
1 3
1 4

Output:

R B
B B R B
R B B B B