시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB158575137.500%

문제

매드 사이언티스트 승혁이는 어느 날 문기를 곯려주고 싶어졌다. 그래서 선물로 위장한 폭탄을 선사하려고 한다. 승혁이는 격자판을 하나 준비하여 하나의 칸에 잘 폭발하는 원소 하나씩을 넣는다. 하나의 원소를 중복 사용할 수도 있다.

그런데 이들 중 어떤 쌍은 인접하는 순간 격렬하게 폭발을 일으킨다. 선물을 건네주기 전에 폭발하면 안 되므로 일단은 폭발이 일어나지 않게 원소들을 배치해야 한다. 문기가 선물을 받고 격렬하게 좋아하며 이리 뛰고 저리 뛰어다니는 동안 이 원소들이 뒤섞여서 무수한 반응을 일으키며 폭발하게 될 것이다.

또한 문기는 선물이 크면 클수록 좋아하지만 정사각형이 아니면 받지 않는다. 그래서 승혁이는 최대한 큰 크기의, 정사각형 모양의 격자판을 선물하려고 한다.

각 원소 종류는 하나의 알파벳 소문자로 표현한다. 따라서 최대 26개의 원소를 사용할 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 폭발하는 쌍의 개수 n이 주어지고(0 ≤ n ≤ 676), 이어서 n개의 줄에 각 쌍의 정보가 알파벳 소문자 2개로 주어진다. 이 두 원소가 인접해 있으면 폭발한다는 뜻이다.

출력

각 테스트 케이스마다 정답을 아무거나 출력한다. 여러 가지 크기가 가능할 경우 그 중 가장 큰 것이 정답이지만, 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
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

예제 출력 1

aw
wz
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
W3sicHJvYmxlbV9pZCI6Ijk1NDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWQwYzQgXHViYzFiXHVjNTQ0XHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5ZTRcdWI0ZGMgXHVjMGFjXHVjNzc0XHVjNWI4XHVkMmYwXHVjMmE0XHVkMmI4IFx1YzJiOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM1YjRcdWIyOTAgXHViMGEwIFx1YmIzOFx1YWUzMFx1Yjk3YyBcdWFjZWZcdWI4MjRcdWM4ZmNcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjMTIwXHViYjNjXHViODVjIFx1YzcwNFx1YzdhNVx1ZDU1YyBcdWQzZWRcdWQwYzRcdWM3NDQgXHVjMTIwXHVjMGFjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMmI5XHVkNjAxXHVjNzc0XHViMjk0IFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjOTAwXHViZTQ0XHVkNTU4XHVjNWVjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWNlNzhcdWM1ZDAgXHVjNzk4IFx1ZDNlZFx1YmMxY1x1ZDU1OFx1YjI5NCBcdWM2ZDBcdWMxOGMgXHVkNTU4XHViMDk4XHVjNTI5XHVjNzQ0IFx1YjEyM1x1YjI5NFx1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWM5MTFcdWJjZjUgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWM3NzRcdWI0ZTQgXHVjOTExIFx1YzViNFx1YjVhNCBcdWMzMGRcdWM3NDAgXHVjNzc4XHVjODExXHVkNTU4XHViMjk0IFx1YzIxY1x1YWMwNCBcdWFjYTlcdWI4MmNcdWQ1NThcdWFjOGMgXHVkM2VkXHViYzFjXHVjNzQ0IFx1Yzc3Y1x1YzczY1x1ZDBhOFx1YjJlNC4gXHVjMTIwXHViYjNjXHVjNzQ0IFx1YWM3NFx1YjEyNFx1YzhmY1x1YWUzMCBcdWM4MDRcdWM1ZDAgXHVkM2VkXHViYzFjXHVkNTU4XHViYTc0IFx1YzU0OCBcdWI0MThcdWJiYzBcdWI4NWMgXHVjNzdjXHViMmU4XHVjNzQwIFx1ZDNlZFx1YmMxY1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWJjMzBcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJiMzhcdWFlMzBcdWFjMDAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YmMxYlx1YWNlMCBcdWFjYTlcdWI4MmNcdWQ1NThcdWFjOGMgXHVjODhiXHVjNTQ0XHVkNTU4XHViYTcwIFx1Yzc3NFx1YjlhYyBcdWI2ZjBcdWFjZTAgXHVjODAwXHViOWFjIFx1YjZmMFx1YzViNFx1YjJlNFx1YjJjOFx1YjI5NCBcdWIzZDlcdWM1NDggXHVjNzc0IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWI0YTRcdWMxMWVcdWM1ZWNcdWMxMWMgXHViYjM0XHVjMjE4XHVkNTVjIFx1YmMxOFx1Yzc1MVx1Yzc0NCBcdWM3N2NcdWM3M2NcdWQwYTRcdWJhNzAgXHVkM2VkXHViYzFjXHVkNTU4XHVhYzhjIFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWJiMzhcdWFlMzBcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzc0IFx1ZDA2Y1x1YmE3NCBcdWQwNzRcdWMyMThcdWI4NWQgXHVjODhiXHVjNTQ0XHVkNTU4XHVjOWMwXHViOWNjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWJhNzQgXHViYzFiXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzJiOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVkMDcwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCwgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFjYTlcdWM3OTBcdWQzMTBcdWM3NDQgXHVjMTIwXHViYjNjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzZkMFx1YzE4YyBcdWM4ODVcdWI5NThcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjZDVjXHViMzAwIDI2XHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkM2VkXHViYzFjXHVkNTU4XHViMjk0IFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAoMCAmbGU7IG4gJmxlOyA2NzYpLCBcdWM3NzRcdWM1YjRcdWMxMWMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzMwZFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MCAyXHVhYzFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjQ1MCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWQzZWRcdWJjMWNcdWQ1NWNcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NzQgXHVjODE1XHViMmY1XHVjNzc0XHVjOWMwXHViOWNjLCAyMCAmdGltZXM7IDIwXHVjZTc4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWFjYTlcdWM3OTBcdWQzMTBcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVhY2JkXHVjNmIwIDIwICZ0aW1lczsgMjBcdWNlNzhcdWM3NzggXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NTQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGlncmFwaHMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZGlncmFwaCBpcyBhIGdyYXBoIHdpdGggb3JpZW50YXRpb24uLi4gb2gsIHNvcnJ5LCBub3QgdGhpcyB0aW1lLiBMZXQmcnNxdW87cyBzdG9wIGJlaW5nIG5lcmRzIGZvciBhIG1pbnV0ZSBhbmQgdGFsayBhYm91dCBsYW5ndWFnZXMgKGh1bWFuIGxhbmd1YWdlcywgbm90IFBIUCkuPFwvcD5cclxuXHJcbjxwPkRpZ3JhcGhzIGFyZSBwYWlycyBvZiBjaGFyYWN0ZXJzIHRoYXQgcmVwcmVzZW50IG9uZSBwaG9uZW1lIChzb3VuZCkuIEZvciBleGFtcGxlLCAmbGRxdW87Y2gmcmRxdW87IGluIEVuZ2xpc2ggKGFzIGluICZsZHF1bztjaHVyY2gmcmRxdW87KSBpcyBhIHNpbmdsZSBjb25zb25hbnQgc291bmQuIFRoZSBsYW5ndWFnZXMgb2YgQ2VudHJhbCBFdXJvcGUgYXJlIGZvbmQgb2YgZGlncmFwaHM6IEh1bmdhcmlhbiAmbGRxdW87c3omcmRxdW87LCBDemVjaCAmbGRxdW87Y2gmcmRxdW87IGFuZCBQb2xpc2ggJmxkcXVvO3J6JnJkcXVvOyBhcmUgZmluZSBleGFtcGxlcyBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5EaWdyYXBocyBhcmUgdmVyeSBhbm5veWluZyBmb3IgcGVvcGxlIHdobyBkbyBub3QgdXNlIHRoZW0gbmF0aXZlbHkuIFdlIHdpbGwgbWFrZSB1cCBhIGxldHRlci1wdXp6bGUgc3BlY2lmaWNhbGx5IGZvciB0aG9zZSBwZW9wbGUuIEdpdmVuIGEgbGlzdCBvZiBkaWdyYXBocywgY29uc3RydWN0IGEgYmlnZ2VzdCBwb3NzaWJsZSBzcXVhcmUgb2YgbG93ZXIgY2FzZSBFbmdsaXNoIGxldHRlcnMgc3VjaCB0aGF0IGl0cyByb3dzIGFuZCBjb2x1bW5zIGRvIG5vdCBjb250YWluIGFueSBvZiB0aGVzZSBkaWdyYXBocy4gVGhpcyBtZWFucyB0aGF0IG5vIHR3byBjb25zZWN1dGl2ZSBsZXR0ZXJzIChyZWFkIGZyb20gdG9wIHRvIGJvdHRvbSBvciBmcm9tIGxlZnQgdG8gcmlnaHQpIGNhbiBmb3JtIGEgZGlncmFwaC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBULiBUaGUgZGVzY3JpcHRpb25zIG9mIHRoZSB0ZXN0IGNhc2VzIGZvbGxvdzo8XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYW4gaW50ZWdlciBuLCAwICZsZTsgbiAmbGU7IDY3NiwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBmb3JiaWRkZW4gZGlncmFwaHMuIFRoZSBuIGZvbGxvd2luZyBsaW5lcyBjb250YWluIHRoZSBkaWdyYXBocy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgYSBzcXVhcmUgb2YgdGhlIGxhcmdlc3QgcG9zc2libGUgc2l6ZSB3aGljaCBkb2VzIG5vdCBjb250YWluIGFueSBvZiB0aGUgZGlncmFwaHMuIElmIGl0IGlzIHBvc3NpYmxlIHRvIGNvbnN0cnVjdCBhIHNxdWFyZSBvZiBzaXplIDIwICZ0aW1lczsgMjAgb3IgYmlnZ2VyLCBwcmludCBvbmx5IGEgMjAgJnRpbWVzOyAyMCBzcXVhcmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Central European Regional Contest > CERC 2013 K번

  • 문제를 번역한 사람: kks227