#P18064. Robots

Robots

Robots

有四种机器人,它们在网格中的移动方式如下。坐标 (x,y)(x,y) 表示第 xx 行、第 yy 列,行号向下增加,列号向右增加。

类型 允许的移动
A 向下 (x+1,y)(x+1,y) 或向右 (x,y+1)(x,y+1)
B 向下 (x+1,y)(x+1,y) 或向左 (x,y−1)(x,y-1)
C 向上 (x−1,y)(x-1,y) 或向右 (x,y+1)(x,y+1)
D 向上 (x−1,y)(x-1,y) 或向左 (x,y−1)(x,y-1)

网格中的 . 表示空格,# 表示障碍。机器人只能放在空格中,并且只能在网格内的空格之间移动。

给定一棵有 NN 个顶点的树,保证每个非叶顶点的度数至少为 44。你需要构造一个 (N+1)×(N+1)(N+1)\times(N+1) 的网格,并放置 NN 个机器人,编号与树的顶点对应。每个机器人的类型可以任意选择,但初始位置必须两两不同。

令 SiS_i 表示第 ii 个机器人能够到达的所有格子的集合,包括它的初始格子。要求对任意两个不同的机器人 i,ji,j:

  • 如果树中存在边 (i,j)(i,j),则 Si∩Sj≠∅S_i\cap S_j\ne\varnothing。
  • 如果树中不存在边 (i,j)(i,j),则 Si∩Sj=∅S_i\cap S_j=\varnothing。

机器人不阻挡彼此的移动。你只需输出一种满足要求的构造。

输入格式

第一行一个整数 TT,表示测试用例数。

每组数据第一行一个整数 NN;接下来 N−1N-1 行,每行两个整数 xi,yix_i,y_i,表示树的一条边。

输出格式

对每组数据:

  • 先输出 N+1N+1 行,每行 N+1N+1 个字符,字符只能是 . 或 #,表示网格。
  • 再输出 NN 行,第 ii 行输出两个整数 xi,yix_i,y_i 和一个字符 cic_i,表示第 ii 个机器人的位置和类型。

所有坐标满足 1≤xi,yi≤N+11\le x_i,y_i\le N+1,$c_i\in\{\texttt{A},\texttt{B},\texttt{C},\texttt{D}\}$。有多种可行方案时,输出任意一种。

数据范围

1≤T≤1031\le T\le10^3,1≤N≤501\le N\le50。输入是一棵树,顶点编号为 11 到 NN。当 N>1N>1 时,每个顶点的度数为 11 或至少 44;N=1N=1 的单顶点树也合法。

样例

1
5
1 2
1 3
1 4
1 5
......
......
......
.##...
..#...
......
6 1 C
1 6 C
1 5 D
2 6 A
2 5 B