L. Robots
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$4$$$ types of robots:

  • A: Can move only down and right. That is, a robot at point $$$(x, y)$$$ can move to point $$$(x + 1, y)$$$ or $$$(x, y + 1)$$$.
  • B: Can move only down and left. That is, a robot at point $$$(x, y)$$$ can move to point $$$(x + 1, y)$$$ or $$$(x, y - 1)$$$.
  • C: Can move only up and right. That is, a robot at point $$$(x, y)$$$ can move to point $$$(x - 1, y)$$$ or $$$(x, y + 1)$$$.
  • D: Can move only up and left. That is, a robot at point $$$(x, y)$$$ can move to point $$$(x - 1, y)$$$ or $$$(x, y - 1)$$$.
There are $$$2$$$ types of cells in the grid:
  • . (Empty): A robot can be freely placed and move through empty cells.
  • # (Blocked): A robot cannot move to blocked cells.
Given a value $$$N$$$, construct a grid of size $$$(N + 1) \times (N + 1)$$$ such that each cell is either empty or blocked. Then place $$$N$$$ robots of any type you want. Robots should be placed in empty cells, and no two robots should be placed in the same cell.

You are also given a tree, where each non-leaf vertex has at least 4 neighbours. Let $$$E$$$ be the set of edges ($$$x_i, y_i$$$). Let $$$S_i$$$ be the set of cells to which robot $$$i$$$ can move. The following conditions should be satisfied:

  • For all pairs $$$(i, j) \in E$$$, $$$S_i \cap S_j \neq \emptyset$$$ must hold.
  • For all pairs $$$(i, j) \notin E$$$, $$$S_i \cap S_j = \emptyset$$$ must hold.
Input
  • The first line contains one integer $$$T \ (1 \leq T \leq 10^3)$$$, the number of tests.
  • Then, for each test:
    • The first line contains one integer $$$N \ (1 \leq N \leq 50)$$$.
    • Then, $$$N - 1$$$ lines follow, each containing two space-separated integers $$$x_i, y_i \ (1 \leq x_i, y_i \leq N)$$$.
Output

For each test, print the answer in the following format:

  • First, print $$$N + 1$$$ lines, each containing $$$N + 1$$$ characters consisting of $$$\texttt{.}$$$ or $$$\texttt{\#}$$$. The $$$j$$$-th character in the $$$i$$$-th line $$$(1 \leq j \leq N + 1, 1 \leq i \leq N + 1)$$$ should represent the type of cell at position $$$(i, j)$$$.
  • Then, print $$$N$$$ lines, each containing two space-separated integers and one character $$$A_i, B_i, C_i$$$ $$$(1 \leq A_i, B_i \leq N + 1; C_i \in \{\texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}\})$$$, where $$$(A_i, B_i)$$$ is the cell where the $$$i$$$-th robot is placed, and $$$C_i$$$ is the type of robot. Note that all robots must be placed in different cells.
Example
Input
1
5
1 2
1 3
1 4
1 5
Output
......
......
......
.##...
..#...
......
6 1 C
1 6 C
1 5 D
2 6 A
2 5 B
Note

Figure 1. Specification for sample.