Square Letter Puzzle

Given a list of forbidden digraphs (two‐letter strings), construct the largest possible square (n×n) of lowercase English letters such that no row or column contains any forbidden digraph as two consecutive characters. In other words, if you read any row left to right or any column top to bottom, no two adjacent letters should form one of the forbidden digraphs.

The input begins with an integer k indicating the number of forbidden digraphs, followed by k lines each containing a two‐letter string. You are to output a square as follows:

• The first line contains an integer n, which is the side length of the square.
• Then follow n lines, each line containing a string of n lowercase English letters. Both the horizontal adjacent pairs (within each row) and the vertical adjacent pairs (in each column) must not be one of the forbidden digraphs.

Note: A 1×1 square is always valid (since no adjacent pair exists), but a larger square may be impossible if the restrictions force a maximum chain length. Your task is to construct the square with the maximum possible n (with n up to 5 for the constraints of this problem). If multiple solutions exist, output the lexicographically smallest one according to the following backtracking strategy: pre-generate all candidate rows (of length n) that are valid horizontally (i.e. they do not contain any forbidden adjacent pair), sorted in lexicographical order, and then choose rows one by one ensuring that the vertical adjacent pairs with the previously chosen row are also valid.

In our solutions we try n = 5,4,3,2,1 in that order and output the first (largest) valid square found.

inputFormat

The first line of input contains an integer k (k ≥ 1) specifying the number of forbidden digraphs. Each of the next k lines contains a forbidden digraph consisting of exactly two lowercase English letters.

outputFormat

Output the maximum possible integer n (1 ≤ n ≤ 5) for which a valid square exists, followed by n lines each containing a string of n lowercase letters. Each row’s adjacent letters and each column’s adjacent letters must not form any of the forbidden digraphs provided in the input.

sample

1
aa

5
ababa
babab
ababa
babab
ababa