Problem I
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$, $1 \leq T \leq 111$. The descriptions of the test cases follow:
Each test case starts with an integer $n$, $0 \leq n \leq 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 \times 20$ or bigger, print only a $20 \times 20$ square.
| Sample Input 1 | Sample Output 1 |
|---|---|
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 oe of og oh oi oj ok ol om on oo op oq or os ot ou ov ow ox oy pa pb pc pd pe pf pg ph pi pj pk pl pm pn po pp pq pr ps pt pu pv pw px py qa qb qc qd qe qf qg qh qi qj qk ql qm qn qo qp qq qr qs qt qu qv qw qx qy ra rb rc rd re rf rg rh ri rj rk rl rm rn ro rp rq rr rs rt ru rv rw rx ry sa sb sc sd se sf sg sh si sj sk sl sm sn so sp sq sr ss st su sv sw sx sy ta tb tc td te tf tg th ti tj tk tl tm tn to tp tq tr ts tt tu tv tw tx ty ua ub uc ud ue uf ug uh ui uj uk ul um un uo up uq ur us ut uu uv uw ux uy va vb vc vd ve vf vg vh vi vj vk vl vm vn vo vp vq vr vs vt vu vv vw vx vy wa wb wc wd we wf wg wh wi wj wk wl wm wn wo wp wq wr ws wt wu wv ww wx wy xa xb xc xd xe xf xg xh xi xj xk xl xm xn xo xp xq xr xs xt xu xv xw xx xy ya yb yc yd ye yf yg yh yi yj yk yl ym yn yo yp yq yr ys yt yu yv yw yx yy za zb zc zd ze zf zg zh zi zj zk zl zm zn zo zp zq zr zs zt zu zv zw zx zy zz 2 aa bb |
aw wz abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa abababababababababab babababababababababa |