시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 158 | 57 | 51 | 37.500% |
매드 사이언티스트 승혁이는 어느 날 문기를 곯려주고 싶어졌다. 그래서 선물로 위장한 폭탄을 선사하려고 한다. 승혁이는 격자판을 하나 준비하여 하나의 칸에 잘 폭발하는 원소 하나씩을 넣는다. 하나의 원소를 중복 사용할 수도 있다.
그런데 이들 중 어떤 쌍은 인접하는 순간 격렬하게 폭발을 일으킨다. 선물을 건네주기 전에 폭발하면 안 되므로 일단은 폭발이 일어나지 않게 원소들을 배치해야 한다. 문기가 선물을 받고 격렬하게 좋아하며 이리 뛰고 저리 뛰어다니는 동안 이 원소들이 뒤섞여서 무수한 반응을 일으키며 폭발하게 될 것이다.
또한 문기는 선물이 크면 클수록 좋아하지만 정사각형이 아니면 받지 않는다. 그래서 승혁이는 최대한 큰 크기의, 정사각형 모양의 격자판을 선물하려고 한다.
각 원소 종류는 하나의 알파벳 소문자로 표현한다. 따라서 최대 26개의 원소를 사용할 수 있다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 폭발하는 쌍의 개수 n이 주어지고(0 ≤ n ≤ 676), 이어서 n개의 줄에 각 쌍의 정보가 알파벳 소문자 2개로 주어진다. 이 두 원소가 인접해 있으면 폭발한다는 뜻이다.
각 테스트 케이스마다 정답을 아무거나 출력한다. 여러 가지 크기가 가능할 경우 그 중 가장 큰 것이 정답이지만, 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 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