Digraphs
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 data
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 data
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.
Examples
2 628 aa az ba bb bc bd be bf bg bh bi bj bk bl bm bn bo bp bq br bs bt bu bv bw bx by ca cb cc cd ce cf cg ch ci cj ck cl cm cn co cp cq cr cs ct cu cv cw cx cy da db dc dd de df dg dh di dj dk dl dm dn do dp dq dr ds dt du dv dw dx dy ea eb ec ed ee ef eg eh ei ej ek el em en eo ep eq er es et eu ev ew ex ey fa fb fc fd fe ff fg fh fi fj fk fl fm fn fo fp fq fr fs ft fu fv fw fx fy ga gb gc gd ge gf gg gh gi gj gk gl gm gn go gp gq gr gs gt gu gv gw gx gy ha hb hc hd he hf hg hh hi hj hk hl hm hn ho hp hq hr hs ht hu hv hw hx hy ia ib ic id ie if ig ih ii ij ik il im in io ip iq ir is it iu iv iw ix iy ja jb jc jd je jf jg jh ji jj jk jl jm jn jo jp jq jr js jt ju jv jw jx jy ka kb kc kd ke kf kg kh ki kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky la lb lc ld le lf lg lh li lj lk ll lm ln lo lp lq lr ls lt lu lv lw lx ly ma mb mc md me mf mg mh mi mj mk ml mm mn mo mp mq mr ms mt mu mv mw mx my na nb nc nd ne nf ng nh ni nj nk nl nm nn no np nq nr ns nt nu nv nw nx ny oa ob oc od o ...
aw wz abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa