Grid Child Game Attribute Reconstruction

There are $n$ children playing a game in a magical space. Each child has a unique name consisting of exactly 3 printable ASCII characters (with ASCII codes from 32 to 126). Each child also possesses k attributes (where k is a non‐negative integer) and for the i-th attribute the value is a positive integer in the range 1 to $a_i$ (with $2 \le a_1 \le a_2 \le \cdots \le a_k$). It is guaranteed that

[ n = a_1 \times a_2 \times \cdots \times a_k, ]

and for any two distinct children, there is at least one attribute in which their values differ.

Two children are said to "know each other" if and only if they differ in exactly one attribute and in that attribute the two values differ by exactly 1 (i.e. the difference is 1). Let m denote the number of unordered pairs of children that know each other.

You are given an integer m and the list of these m relation pairs (each pair consists of two names of children who know each other). Your task is to find one possible set of parameters: the number k and the sequence \(a_1, a_2, \dots, a_k\) satisfying the above conditions.

inputFormat

The input is given as follows:

1. The first line contains an integer m, the number of pairs of children who know each other.
2. Each of the next m lines contains two strings (each of exactly 3 characters) separated by a space, denoting the names of two children who know each other.

You can assume that the overall number of children n (which is the number of distinct names that appear) satisfies \(n = a_1 \times a_2 \times \cdots \times a_k\) for some sequence \(a_1, a_2, \dots, a_k\) with \(2 \le a_1 \le a_2 \le \cdots \le a_k\). Moreover, the given relations are exactly those between children whose attribute values differ in exactly one coordinate by 1.

outputFormat

Output one possible solution in a single line: first output the integer k (the number of attributes), followed by k space‐separated integers \(a_1, a_2, \dots, a_k\). If there are multiple valid answers, any one is acceptable.

Note: It is guaranteed that the input corresponds to a valid grid configuration.

sample

4
A01 A02
A02 A03
A03 A04
A04 A05

1 5