Overview

For each tree, we enumerate as a set all possible traversal records that can be created by freely changing the visitation order of children.
Then, we take the intersection of the two sets and output the results in lexicographic order.

Analysis

A traversal record is a parenthesis-like string produced by DFS on a rooted tree, writing a when entering a node and b when leaving it.

For example, if a node is a leaf, its traversal record is always:

ab

On the other hand, if a node \(v\) has multiple children, we can freely rearrange the order in which the children are visited.
Moreover, within each child’s subtree, we can also freely choose the order.

In other words, the traversal record for node \(v\) can be constructed as follows:

1. Determine the set of possible traversal records for each child subtree
2. Try all permutations of the children’s visitation order
3. For each ordering, select one traversal record from each child and concatenate them
4. Prepend a at the beginning and append b at the end

For example, if the children’s traversal records are ab and aabb respectively, depending on the order we get different strings:

a + ab + aabb + b = aabaabbb
a + aabb + ab + b = aaabbabb

However, when there are multiple children with the same structure, different visitation orders may produce the same string.
Since the problem requires output without duplicates, we manage the generated strings using a set.

The constraint is \(N \leq 10\), which is very small, so exhaustively enumerating all traversal records for each tree is fast enough.

Algorithm

First, since the input tree is given as an undirected graph, we root it at room \(1\) to establish parent-child relationships.

Then, we consider the following recursive function.

dfs(v)

Returns the set of traversal records that can be produced from the subtree rooted at node \(v\).

• If \(v\) is a leaf, the returned set is {"ab"}
• Otherwise:
  • Compute dfs(c) for each child \(c\)
  • Try all permutations of the children’s ordering
  • For each ordering, try all combinations of selecting one traversal record from each child
  • Concatenate them to form a + children's records + b and add to the set

In the code, permutations is used to enumerate all orderings of the children, and product is used to enumerate all ways of selecting traversal records for each child.

Finally,

records_a = generate_records(adj_a)
records_b = generate_records(adj_b)
common = sorted(records_a & records_b)

we take the intersection of the traversal record sets obtained from the two trees and sort them in lexicographic order.

In Python’s string comparison, 'a' < 'b' holds, so using sorted directly gives us the lexicographic order as defined in the problem.

Complexity

• Time complexity: \(O\left(\sum_v d_v! \prod_{c} R_c \cdot s_v + K \log K \cdot N\right)\)
• Space complexity: \(O\left(\sum_v R_v \cdot s_v\right)\)

Where:

• \(d_v\) is the number of children of node \(v\)
• \(R_v\) is the number of traversal records producible from the subtree rooted at node \(v\)
• \(s_v\) is the subtree size of node \(v\)
• \(K\) is the number of common traversal records

Each candidate string has length at most \(2N\), so string concatenation and sort comparisons take about \(O(N)\) time.
However, since the constraint is \(N \leq 10\), exhaustive enumeration is sufficiently fast.

Implementation Notes

• Since the input tree consists of undirected edges, first search from root \(1\) to build children

• Manage traversal records for each subtree using a set to eliminate duplicates

• The traversal record for a leaf is always {"ab"}

• Try all orderings of children using permutations

• Try all ways of selecting traversal records for each child using product

• Finally, take the set intersection records_a & records_b and sort with sorted for lexicographic order

  Source Code

import sys
from itertools import permutations, product

def generate_records(adj):
    n = len(adj)
    children = [[] for _ in range(n)]
    parent = [-1] * n
    parent[0] = -2
    stack = [0]

    for v in stack:
        for to in adj[v]:
            if parent[to] == -1:
                parent[to] = v
                children[v].append(to)
                stack.append(to)

    sys.setrecursionlimit(10000)

    def dfs(v):
        if not children[v]:
            return {"ab"}

        child_sets = [dfs(c) for c in children[v]]
        k = len(child_sets)
        res = set()

        for perm in permutations(range(k)):
            ordered_sets = [child_sets[i] for i in perm]
            for parts in product(*ordered_sets):
                res.add("a" + "".join(parts) + "b")

        return res

    return dfs(0)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    idx = 1

    adj_a = [[] for _ in range(n)]
    for _ in range(n - 1):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        idx += 2
        adj_a[u].append(v)
        adj_a[v].append(u)

    adj_b = [[] for _ in range(n)]
    for _ in range(n - 1):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        idx += 2
        adj_b[u].append(v)
        adj_b[v].append(u)

    records_a = generate_records(adj_a)
    records_b = generate_records(adj_b)

    common = sorted(records_a & records_b)

    out = [str(len(common))]
    out.extend(common)
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.