Digraphs
A digraph is a graph with orientation... oh, sorry, not this time. Let’s stop being nerds for a minute and talk about languages (human languages, not PHP).
Digraphs are pairs of characters that represent one phoneme (sound). For example, "ch" in English (as in "church") is a single consonant sound. The languages of Central Europe are fond of digraphs: Hungarian "sz", Czech "ch" and Polish "rz" are fine examples of them.
Digraphs are very annoying for people who do not use them natively. We will make up a letter-puzzle specifically for those people. Given a list of digraphs, construct a biggest possible square of lower case English letters such that its rows and columns do not contain any of these digraphs. This means that no two consecutive letters (read from top to bottom or from left to right) can form a digraph.
Input
The first line of input contains the number of test cases T. The descriptions of the test cases follow:
Each test case starts with an integer n, 0 ≤ n ≤ 676, denoting the number of forbidden digraphs. The n following lines contain the digraphs.
Output
For each test case print a square of the largest possible size which does not contain any of the digraphs. If it is possible to construct a square of size 20×20 or bigger, print only a 20×20 square.
Warning: Part of the example test data below was omitted for clarity. You can access full sample tests at your workstation.