← 返回题目列表

AtCoder · tenka1_2016_qualA_d

D. 图表

中文机器翻译题面 查看原题

配点 : 1100 点

問題文

Tenkaichi Co., Ltd. 开发可直观地表示图论中的图形的软件。 特别是,以易于阅读的基于文本的格式显示不太复杂的图形的工具很受欢迎。

N 给出一棵无向顶点树。 每个顶点都分配有一个不重复的大写字母(顶点数为 26 如下)。

N-1 书内 i th 是顶点 v_i 与 边缘 w_i 。 然而,对于任何顶点,连接到该顶点的边的数量是 4 保证:

编写一个程序,直观地显示给定的树,如下所示。 输出部分提供了详细信息。

8 12
............
...D...E....
...|...|....
.C-A---B---F
.|.....|...|
.|.....G.J-I
.H..........
............

制約

  • 2≦N≦26
  • v_i, w_i 是第一个大写字母 N 是字符之一。
  • 给定的图是一棵树。
  • 对于任何顶点,连接到该顶点的边数为 4 下面。

入力

输入是按以下格式从标准输入给出的。

N
v_1 w_1
v_2 w_2
:
v_{N-1} w_{N-1}

出力

按以下格式输入树。 将其显示在 H+1 行上。

H W
c_{1,1}c_{1,2} … c_{1,W}
c_{2,1}c_{2,2} … c_{2,W}
:
c_{H,1}c_{H,2} … c_{H,W}

在这里,

  • H, W 表示随后的视觉显示的大小,由单个半角空格分隔。 必须满足1≦H≦100, 1≦W≦100 。
  • 视觉显示为 H 文字、横 W 这是一个矩形的字符排列。
  • 组成视觉显示的每个字符 c_{i,j} 是第一个大写字母 N 字符和 .、-、| 并满足以下条件。
    • 树的每个顶点都由相应的大写字母表示。每个顶点必须在视觉显示中恰好出现一次。
    • 表示一个顶点的字符不得与表示另一个顶点的字符垂直或水平相邻。
    • 两个顶点 如果 a, b 由一条边直接连接,则以下条件 (A), (B) 必须满足 之一。 代表
      • (A) 頂点 a, b 的两个字符在视觉显示的同一行上,并且它们之间的所有字符都是 代表 - 。
      • (B) 必须满足 頂点 a, b 的两个字符位于视觉显示的同一列中,并且它们之间的所有字符都是 如果 | 。
    • 两个顶点 如果 a, b 不是由一条边直接连接,则上述条件 (A), (B) 必须满足 均被禁止。
    • 如上所示,除了表示顶点和边的字符之外的所有字符 必须是 . 。 当

可以证明,对于满足约束的输入,总是存在满足这些条件的视觉显示。可以输出任何这样的视觉显示。


入力例 1

10
A B
A C
A D
B E
B F
B G
C H
F I
I J

出力例 1

8 12
............
...D...E....
...|...|....
.C-A---B---F
.|.....|...|
.|.....G.J-I
.H..........
............

输出示例与问题文本中显示的示例相同。


入力例 2

7
A B
B C
C D
D E
E F
F G

出力例 2

5 4
.A-B
E-F|
|.||
|.G|
D--C

代表顶点的字符是 不禁止与 - 呀 请注意,它可能是 | 垂直或水平相邻。