Christopher's "Wedding"

Time Limit: 4 Seconds    Memory Limit: 32768 KB
Special Judge

Christopher attends the wedding ceremony for the first time. Woefully, this is his lover's wedding ceremony, but not his. He pretends as an electrician, to see his lover's face last time. In order not to be come to light, he asks a real electrician to accompany him to the wedding. At the most shorthanded time, he is forced to use soldering iron to connect some connecting point on a circuit board, even he has tried to excuse that he's only a jackaroo for many times.

Another way:

As the graph, the circuit board is a two-sided board, but only one dimension in planform. Christopher is asked to connect m fixed pairs of connecting points. Of coz we know the iron wires connecting points could NEVER intersect, that is, on the same side of the board, there could NEVER be such two pairs of connecting iron wires (a, b) and (c, d), and a < c < b < d.

Christopher could use soldering iron well by his courses in University, but the only one professional course he hasn't learnt (that's the professional electrician's course), is how to connect them well with only TWO sides!

Christopher doesn't want to be come to light, so he took his laptop out, with wireless internet supported. The electrical soldering iron is switched on, the smell of melted soldering tin dance to the round. You'd better help him as quickly as possible.

Input

The first line of input contains a number X (1 <= X <= 14) which denotes the number of test cases. For each test case:

Line 1: n (1 <= n <= 20,000) - number of the connecting points on the circuit board, m (1 <= m <= 20,000) - total number of pairs of points that should be connected.

Line 2~m+1: two integers a and b (1 <= a < b <= i), denote a pair of points that should be connected. (points are numbered 1~n from left to right)

There're NO breakline between two continuous test cases.

Output

For each test case, you should output a single line with "Impossible" (Without quotation) if there's NO solution for that case. If there's at least one solution, you could output it (ANY one) in the following format:

M lines in total, each line contains a single letter "U" or "D" denotes the side UP or DOWN for the iron wire to connect corresponding pair of points (i.e. the same order in input).

There're NO breakline between two continuous test cases.

Sample Input

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

Sample Output

U
D
U
D
U
U
U
D
D
D

Submit

Source: Online Contest of Christopher's Adventure