One-Character Difference Sequence

You are given a list of strings. Your task is to determine whether it is possible to rearrange the strings into a sequence such that every two consecutive strings differ by exactly one character. In other words, for every two adjacent strings s_i and s_i+1, if we compare them character by character, exactly one position should have a different character. This can be written in \( \LaTeX \) as:

[ \forall, i,\ 1 \le i < n:\quad #{j \mid s_{i}[j] \neq s_{i+1}[j]} = 1 ]

If there exists such a rearrangement, output "True"; otherwise, output "False".

inputFormat

The input is read from standard input (stdin) and has the following format:

n
s1
s2
... 
sn

Here, n is the number of strings, and each of the following n lines contains a single string. All strings are guaranteed to have the same length.

outputFormat

The output is written to standard output (stdout). Print a single line containing either "True" if it is possible to rearrange the strings into a valid sequence or "False" otherwise.

3
abc
bbc
bac

True