D - Common Tour Record Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君と青木君は、それぞれ N 個の部屋からなる施設を管理しています。各施設の部屋は木構造の通路で結ばれており、どちらも部屋 1 が入口（根）です。通路は双方向に通行可能であり、部屋 1 を根として各部屋の親子関係が定まります。

N 個の部屋からなる根付き木に対して、巡回記録を以下の手順で定義します。

  1. 各部屋について、その部屋の子の部屋（直接通路で繋がる、根からより遠い側の部屋）を訪れる順番を決める。この順番は部屋ごとに任意に決めてよい。
  2. 空文字列から始めて、入口（部屋 1）に対して以下の再帰的手順を実行し、得られた文字列を巡回記録とする。

部屋 v に対する再帰的手順：

  • まず、文字 a を末尾に追加する。
  • 次に、手順1で決めた順番に従い、部屋 v の子の部屋それぞれに対して順に以下を行う：その子の部屋に対してこの再帰的手順を実行する（部屋 v に戻る際に文字の追加は行わない）。
  • 最後に、文字 b を末尾に追加する。

部屋 v が子を持たない場合、2番目の処理で何もせず、a の直後に b が追加されます。

このようにして得られる文字列の長さは常に 2N です。

子の訪問順序の選び方によって、異なる巡回記録が得られることがあります。高橋君の施設から得られるすべての巡回記録の集合と、青木君の施設から得られるすべての巡回記録の集合の共通部分に含まれる文字列を、共通巡回記録と呼びます。

すべての共通巡回記録を辞書順に列挙してください。ただし、異なる子の訪問順序から同一の文字列が得られる場合は重複なく 1 つだけ出力します。文字の大小は 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}
  • 1 行目には、施設の部屋数を表す整数 N が与えられる。
  • 続く N - 1 行では、高橋君の施設の通路が与えられる。
  • そのうち i 行目 (1 \leq i \leq N-1) には、高橋君の施設の i 番目の通路が結ぶ 2 つの部屋の番号を表す整数 UA_i, VA_i がスペース区切りで与えられる。
  • さらに続く N - 1 行では、青木君の施設の通路が与えられる（高橋君の施設の辺の直後に空行を挟まず続く）。
  • そのうち i 行目 (1 \leq i \leq N-1) には、青木君の施設の i 番目の通路が結ぶ 2 つの部屋の番号を表す整数 UB_i, VB_i がスペース区切りで与えられる。

N = 1 のときは辺の行は存在しない。

出力

共通巡回記録の個数を K とする。

まず 1 行目に K を出力せよ。共通巡回記録が存在しない場合は 0 を出力し、それ以降は何も出力しない。

K \geq 1 の場合、続く K 行に、すべての共通巡回記録を辞書順に 1 行に 1 つずつ出力せよ。

入力例 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

Score : 400 pts

Problem Statement

Takahashi and Aoki each manage a facility consisting of N rooms. The rooms in each facility are connected by corridors forming a tree structure, and in both facilities, room 1 is the entrance (root). Corridors can be traversed in both directions, and the parent-child relationships of the rooms are determined by taking room 1 as the root.

For a rooted tree consisting of N rooms, a traversal record is defined by the following procedure:

  1. For each room, determine the order in which to visit its child rooms (rooms directly connected by a corridor that are farther from the root). This order may be chosen arbitrarily for each room.
  2. Starting from an empty string, execute the following recursive procedure on the entrance (room 1), and the resulting string is the traversal record.

Recursive procedure for room v:

  • First, append the character a to the end.
  • Next, following the order determined in step 1, for each child room of room v, do the following in order: execute this recursive procedure on that child room (no characters are appended when returning to room v).
  • Finally, append the character b to the end.

If room v has no children, nothing is done in the second step, and b is appended immediately after a.

The length of the string obtained in this way is always 2N.

Depending on the choice of visiting order of children, different traversal records may be obtained. A string that belongs to the intersection of the set of all traversal records obtainable from Takahashi's facility and the set of all traversal records obtainable from Aoki's facility is called a common traversal record.

Enumerate all common traversal records in lexicographic order. If the same string is obtained from different child visiting orders, output it only once without duplication. The character ordering is a < b.

Constraints

  • 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)
  • The corridors of Takahashi's facility form a tree structure (N rooms connected by N-1 undirected edges)
  • The corridors of Aoki's facility form a tree structure (N rooms connected by N-1 undirected edges)
  • All input values are integers

Input

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}
  • The first line contains an integer N representing the number of rooms in each facility.
  • The following N - 1 lines give the corridors of Takahashi's facility.
  • The i-th of these lines (1 \leq i \leq N-1) contains integers UA_i and VB_i, separated by a space, representing the two rooms connected by the i-th corridor of Takahashi's facility.
  • The next N - 1 lines give the corridors of Aoki's facility (immediately following the edges of Takahashi's facility with no blank line in between).
  • The i-th of these lines (1 \leq i \leq N-1) contains integers UB_i and VB_i, separated by a space, representing the two rooms connected by the i-th corridor of Aoki's facility.

When N = 1, no edge lines exist.

Output

Let K be the number of common traversal records.

First, output K on the first line. If no common traversal records exist, output 0 and output nothing further.

If K \geq 1, output all common traversal records in lexicographic order on the following K lines, one per line.

Sample Input 1

3
1 2
1 3
1 2
1 3

Sample Output 1

1
aababb

Sample Input 2

3
1 2
2 3
1 2
1 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2
aaababbaabbb
aaabbaababbb

Sample Input 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

Sample Output 4

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

Sample Input 5

1

Sample Output 5

1
ab