题目描述

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.

输入格式

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 \le n \le 676$ , denoting the number of forbidden digraphs. The $n$ following lines contain the digraphs.

输出格式

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.

Warning: Part of the example test data below was omitted for clarity. You can access full sample tests at your workstation.

题目大意

题目描述

有一些有向字母对，构造一个尽量大（最大$20\times20$）的方阵，使得这个方阵中任意两个相邻字母对（从左到右或从上到下）都不是这些有向字母对中的一个。

输入格式

第一行一个整数$T$，表示数据组数。

每组数据第一行一个整数$n$($0 \le n \le 676$)，表示有向字母对数。

接下来$n$行，每行$2$个小写字母，表示一组有向字母对。

输出格式

对于每组数据，输出一个尽量大的方阵，不包含任何一个有向字母对（如果可以构造比$20\times20$规模更大的方阵，只需要$20\times20$规模就够了）。

如果有多组解，输出任意一组即可。

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

提示

Time limit: 2 s, Memory limit: 128 MB.