Диграфы
Диграфы
Диграф - это ориентированный граф... о нет, не в этот раз. Давайте на минуту перестанем быть умниками и поговорим о языках (человеческих языках, не PHP).
Диграф - это пара букв, представляющих собой одну фонему (звук). Например, "ch" в английском (как и в "church") - один согласный звук. Языки центральной Европу полны диграфов: венгерское "sz", чешское "ch" и польское "rz" лучшие их представители.
Диграфы очень раздражают людей, которые не используют их изначально. Специально для таких людей мы составим письмо-загадку. По заданному списку диграфов необходимо составить наибольший возможный квадрат строчных букв английского алфавита таким образом, чтобы его строки и колонки не содержали ни один из этих диграфов. То есть никакие две последовательные буквы (если читать сверху вниз или слева направо) не образуют диграф.
Вхідні дані
Первая строка содержит количество тестов t. Структура каждого теста следующая:
Каждый тест начинается с количества n (0 ≤ n ≤ 676) запрещенных диграфов. Следующие n строк содержат диграфы.
Вихідні дані
Для каждого теста вывести квадрат максимально возможного размера, который не содержит в себе диграфов. Если можно построить квадрат размером 20×20 или больше, выведите только квадрат 20×20.
Приклад
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