eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Диграфы

Диграфы

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Диграф - это ориентированный граф... о нет, не в этот раз. Давайте на минуту перестанем быть умниками и поговорим о языках (человеческих языках, не PHP).

Диграф - это пара букв, представляющих собой одну фонему (звук). Например, "ch" в английском (как и в "church") - один согласный звук. Языки центральной Европу полны диграфов: венгерское "sz", чешское "ch" и польское "rz" лучшие их представители.

Диграфы очень раздражают людей, которые не используют их изначально. Специально для таких людей мы составим письмо-загадку. По заданному списку диграфов необходимо составить наибольший возможный квадрат строчных букв английского алфавита таким образом, чтобы его строки и колонки не содержали ни один из этих диграфов. То есть никакие две последовательные буквы (если читать сверху вниз или слева направо) не образуют диграф.

Вхідні дані

Первая строка содержит количество тестов t. Структура каждого теста следующая:

Каждый тест начинается с количества n (0n676) запрещенных диграфов. Следующие n строк содержат диграфы.

Вихідні дані

Для каждого теста вывести квадрат максимально возможного размера, который не содержит в себе диграфов. Если можно построить квадрат размером 20×20 или больше, выведите только квадрат 20×20.

Приклад

Вхідні дані #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
o
...
Вихідні дані #1
aw
wz
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
Джерело 2013 ACM ICPC Central Europe Regional Contest, Краков, Ноябрь 15-17, Задача K