Parallel Evolution Verification

It is the year 2178 and fossil evidence from an alien planet has raised an exciting hypothesis: parallel evolution. According to the hypothesis, the currently observed species has evolved along two independent evolutionary paths from two different single‐nucleotide ancestors, but finally both paths converged into the same modern genetic sequence. In each path, evolution takes place by inserting a single nucleotide into the genetic sequence. The available fossil record consists of genetic sequences composed of three types of nucleotides: A (Adenine), C (Cytosine) and M (Muamine).

Formally, a valid evolutionary chain is a sequence of strings
\( s_1, s_2, \ldots, s_L \) such that:

• \( |s_1| = 1 \) (a single nucleotide);
• for each \( 2 \le i \le L \), \( s_i \) is obtained by inserting exactly one nucleotide into \( s_{i-1} \); that is, there exists an index \( j \) (with \( 0 \leq j \leq |s_{i-1}|\)) such that
  \( s_i = s_{i-1}[0:j] + X + s_{i-1}[j:] \) for some nucleotide \( X \in \{A, C, M\} \).

The parallel evolution hypothesis asserts that the complete set of fossil samples can be partitioned into two evolutionary chains whose elements satisfy the above conditions, with the additional constraint that both chains share the same final genetic sequence. Since the two chains are disjoint except for the shared final sequence, if the maximum length of any fossil sequence is \( L \), then the total number of fossils must be exactly
\( 2L - 1 \).

Your task is to determine, given the fossil record, whether it is possible to explain all the fossils by two evolutionary chains as described. In other words, check whether all fossils can be partitioned into two chains with the following properties:

• One chain is
  \( s^1_1, s^1_2, \ldots, s^1_L \)
• the other is
  \( s^2_1, s^2_2, \ldots, s^2_L \)
• For each chain, for \( i \ge 2 \), \( s^k_i \) is obtained by inserting exactly one nucleotide into \( s^k_{i-1} \).
• \( s^1_L = s^2_L \) (the final fossil is common) and all other fossils appear exactly once among the two chains.

If the fossil record satisfies these conditions, output 1; otherwise, output 0.

Note: All valid transformations must satisfy the relation \[ s \to t \quad \text{if and only if} \quad |t| = |s|+1 \text{ and there exists an index } j \text{ such that } t = s[0:j] + X + s[j:], \; X\in\{A,C,M\}. \]

inputFormat

The input begins with an integer \( n \) indicating the number of fossil samples. The following \( n \) lines each contain a non‐empty string consisting only of the characters 'A', 'C', and 'M'. The fossils may be given in arbitrary order.

Note: If \( L_{max} \) is the maximum length of any fossil, a necessary (but not sufficient) condition for a valid record is that \( n = 2L_{max} - 1 \>, and additionally, there must be exactly 2 fossils of each length \( 1 \leq l < L_{max} \) and exactly 1 fossil of length \( L_{max} \).

outputFormat

Output a single integer: 1 if the fossil record is consistent with the parallel evolution hypothesis, and 0 otherwise.

sample

5
ACM
AC
AM
M
A

1