[Solution] Ambiguous Dominoes solution codeforces

Ambiguous Dominoes solution codeforces – Polycarp and Monocarp are both solving the same puzzle with dominoes. They are given the same set of 𝑛n dominoes, the 𝑖i-th of which contains two numbers 𝑥𝑖xi and 𝑦𝑖yi. They are also both given the same 𝑚m by 𝑘k grid of values 𝑎𝑖𝑗aij such that 𝑚𝑘=2𝑛m⋅k=2n.

Table of Contents

[Solution] Ambiguous Dominoes solution codeforces

The puzzle asks them to place the 𝑛n dominoes on the grid in such a way that none of them overlap, and the values on each domino match the 𝑎𝑖𝑗aij values that domino covers. Dominoes can be rotated arbitrarily before being placed on the grid, so the domino (𝑥𝑖,𝑦𝑖)(xi,yi) is equivalent to the domino (𝑦𝑖,𝑥𝑖)(yi,xi).

They have both solved the puzzle, and compared their answers, but noticed that not only did their solutions not match, but none of the 𝑛n dominoes were in the same location in both solutions! Formally, if two squares were covered by the same domino in Polycarp’s solution, they were covered by different dominoes in Monocarp’s solution. The diagram below shows one potential 𝑎a grid, along with the two players’ solutions.

Ambiguous Dominoes solution codeforces

[Solution] Ambiguous Dominoes solution codeforces

Polycarp and Monocarp remember the set of dominoes they started with, but they have lost the grid 𝑎a. Help them reconstruct one possible grid 𝑎a, along with both of their solutions, or determine that no such grid exists.

Input

The first line contains a single integer 𝑛n (1𝑛31051≤n≤3⋅105).

The 𝑖i-th of the next 𝑛n lines contains two integers 𝑥𝑖xi and 𝑦𝑖yi (1𝑥𝑖,𝑦𝑖2𝑛1≤xi,yi≤2n).

Output

If there is no solution, print a single integer 1−1.

Otherwise, print 𝑚m and 𝑘k, the height and width of the puzzle grid, on the first line of output. These should satisfy 𝑚𝑘=2𝑛m⋅k=2n.

The 𝑖i-th of the next 𝑚m lines should contain 𝑘k integers, the 𝑗j-th of which is 𝑎𝑖𝑗aij.

[Solution] Ambiguous Dominoes solution codeforces

The next 𝑚m lines describe Polycarp’s solution. Print 𝑚m lines of 𝑘k characters each. For each square, if it is covered by the upper half of a domino in Polycarp’s solution, it should contain a “U”. Similarly, if it is covered by the bottom, left, or right half of a domino, it should contain “D”, “L”, or “R”, respectively.

The next 𝑚m lines should describe Monocarp’s solution, in the same format as Polycarp’s solution.

If there are multiple answers, print any.

Examples
input

Copy
1
1 2
output

Copy
-1
input

Copy
2
1 1
1 2

[Solution] Ambiguous Dominoes solution codeforces

output

Copy
2 2

2 1
1 1

LR
LR

UU
DD
input

Copy
10
1 3
1 1
2 1
3 4
1 5
1 5
3 1
2 4
3 3
4 1

[Solution] Ambiguous Dominoes solution codeforces

output

Copy
4 5

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

LRULR
LRDLR
ULRLR
DLRLR

UULRU
DDUUD
LRDDU
LRLRD
Note

Extra blank lines are added to the output for clarity, but are not required.

The third sample case corresponds to the image from the statement.

For Solution

Click Here

Leave a Comment