No.470 Inverse S+T Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 32
作問者 : ぴろずぴろず / テスター : kimiyukikimiyuki

10 ProblemId : 1425 / 出題時の順位表

問題文

文字列$S,T$に対して、$S$と$T$を結合したものを$S+T$で表します。

$N$個の長さ$3$の文字列$U_1,U_2,\dots,U_N$が与えられます。
$1 \leq i \leq N$について$S_i + T_i = U_i$となるような、$2N$個の相異なる空でない文字列$S_1, S_2, \dots, S_N, T_1, T_2, \dots, T_N$を求めて下さい。

入力

$N$
$U_1$
$U_2$
$\vdots$
$U_N$

$1$行目に文字列の個数$N$が与えられます。
続く$N$行は入力の文字列です。$i+1$行目に$U_i$が与えられます。

$1 \leq N \leq 10^5$
$U_i$は長さ$3$の文字列であり、小文字のaからzまたは大文字のAからZまでの文字のみを含む。

出力

この問題はスペシャルジャッジです。

条件を満たす文字列$S_1, S_2, \dots, S_N, T_1, T_2, \dots, T_N$が存在しない時、Impossibleと出力して下さい。
そうでない時、$1$行目から$N$行目まで、$i$行目に$S_i$と$T_i$をスペース区切りで出力してください。
このとき条件を満たしていればいずれの解も正解とみなされます。
最後に改行してください。

サンプル

サンプル1
入力
3
abc
abd
cbc
出力
a bc
ab d
cb c

$S_1=a, T_1=bc$
$S_2=ab, T_2=d$
$S_3=cb, T_3=c$
とすれば、条件を満たすことができます。
このケースでは、これが唯一の答えです。

サンプル2
入力
2
aaa
aaa
出力
Impossible

条件を満たす$S_i,T_i$が存在しないので、Impossibleを出力します。
$S_i$や$T_i$は空でない必要があることに注意して下さい。

サンプル3
入力
2
aaa
AAA
出力
a aa
A AA

大文字と小文字は区別してください。
a aa
AA A
などの他の答えも存在します。

サンプル4
入力
10
kgb
cih
blm
kee
lgj
dcl
bam
ibc
mca
lkf
出力
k gb
c ih
b lm
ke e
l gj
d cl
ba m
i bc
mc a
lk f

提出ページヘ