← 返回题目列表

AtCoder · awc0111_d

D. 普通巡演记录

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

分数: 400 分

问题陈述

高桥和青木各自管理一个设施,包括 N 房间。每个设施的房间都通过形成树结构的走廊连接,并且在两个设施中,房间 1 是入口(根)。走廊可以双向穿越,通过占用空间来确定房间的亲子关系 1 作为根。

对于由以下组成的有根树 N 房间, 遍历记录 通过以下过程定义:

  1. 对于每个房间,确定访问其子房间(由距离根较远的走廊直接连接的房间)的顺序。该顺序可以为每个房间任意选择。
  2. 从空字符串开始,在入口处(房间 1),得到的字符串就是遍历记录。

房间的递归过程 v:

  • 首先,追加字符 a 到最后。
  • 接下来,按照步骤 1 中确定的顺序,对于房间的每个子房间 v,按顺序执行以下操作:在该子房间上执行此递归过程(返回房间时不附加任何字符 v).
  • 最后,附加字符 b 到最后。

如果房间 v 没有孩子,第二步没有做任何事情,并且 b 紧随其后 a.

这样得到的字符串长度总是 2N.

根据孩子访问顺序的选择,可能会得到不同的遍历记录。属于可从高桥设施获得的所有遍历记录的集合与可从青木设施获得的所有遍历记录的集合的交集的字符串称为 普通遍历记录.

按字典顺序枚举所有常见的遍历记录。如果不同的子访问顺序得到相同的字符串,则只输出一次,不重复。字符顺序是 a < b.

约束

  • 1 \leq N \leq 10
  • 1 \leq UA_i, VA_i \leq N, UA_i \neq VA_i (1 \leq i \leq N-1)
  • 1 \leq UB_i, VB_i \leq N, UB_i \neq VB_i (1 \leq i \leq N-1)
  • 高桥工厂的走廊形成树状结构(N 房间由以下连接 N-1 无向边)
  • 青木工厂的走廊形成树状结构(N 房间由以下连接 N-1 无向边)
  • 所有输入值均为整数

输入

N
UA_1 VA_1
UA_2 VA_2
:
UA_{N-1} VA_{N-1}
UB_1 VB_1
UB_2 VB_2
:
UB_{N-1} VB_{N-1}
  • 第一行包含一个整数 N 代表每个设施中的房间数量。
  • 以下 N - 1 线给出了高桥工厂的走廊。
  • 的 i- 第这些行 (1 \leq i \leq N-1) 包含整数 UA_i 和 VB_i,以空格分隔,代表由 i高桥工厂的第走廊。
  • 下一个 N - 1 线给出了 Aoki 设施的走廊(紧邻 Takahashi 设施的边缘,中间没有空行)。
  • 的 i- 第这些行 (1 \leq i \leq N-1) 包含整数 UB_i 和 VB_i,以空格分隔,代表由 i青木工厂的第走廊。

当 N = 1,不存在边缘线。

输出

让 K 为普通遍历记录的数量。

一、输出 K 在第一行。如果不存在公共遍历记录,则输出 0 并不再输出任何内容。

If K \geq 1,按字典顺序输出以下所有常见遍历记录 K 行,每行一个。


示例输入 1

3
1 2
1 3
1 2
1 3

示例输出 1

1
aababb

示例输入 2

3
1 2
2 3
1 2
1 3

示例输出 2

0

示例输入 3

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

示例输出 3

2
aaababbaabbb
aaabbaababbb

示例输入 4

10
1 2
1 3
1 4
2 5
2 6
3 7
4 8
5 9
7 10
1 6
1 2
1 3
6 4
6 5
4 8
2 7
7 9
3 10

示例输出 4

12
aaaabbabbaaabbbaabbb
aaaabbabbaabbaaabbbb
aaaabbbaaabbabbaabbb
aaaabbbaabaabbbaabbb
aaaabbbaabbaaabbabbb
aaaabbbaabbaabaabbbb
aaabaabbbaaabbbaabbb
aaabaabbbaabbaaabbbb
aaabbaaabbabbaaabbbb
aaabbaaabbbaaabbabbb
aaabbaaabbbaabaabbbb
aaabbaabaabbbaaabbbb

示例输入 5

1

示例输出 5

1
ab