CF510C.Fox And Names

传统题 时间 2000 ms 内存 256 MiB 7 尝试 32 已通过 8 标签

Fox And Names

题目描述

狐狸 Ciel 打算在 FOCS(Foxes Operated Computer Systems,发音为“Fox”)上发表一篇论文。她听到一个传闻:论文上的作者列表总是按字典序排列的。

但在检查了一些例子后,她发现有时并非如此。有些论文上作者的名字在通常意义下并没有按字典序排列。但她发现,如果对字母表中的字母顺序进行某种调整,作者列表的字典序总是成立的!

现在她想弄清楚,是否存在一种拉丁字母表上的字母顺序,使得她提交的论文上的名字按字典序递增。如果存在,请你找出任意一种这样的顺序。

字典序的定义如下:比较两个字符串 sstt 时,首先找到最左边字符不同的位置 ii,即 sitis_i \ne t_i。如果没有这样的位置(即一个字符串是另一个的前缀),则较短的字符串更小。否则,按照字母表中的顺序比较字符 sis_itit_i

输入

第一行包含一个整数 nn1n1001 \le n \le 100)—— 名字的数量。

接下来 nn 行,每行包含一个字符串 nameiname_i1namei1001 \le |name_i| \le 100),表示第 ii 个名字。每个名字只包含小写拉丁字母。所有名字互不相同。

输出

如果存在一种字母顺序使得给出的名字按字典序排列,则输出任意一个这样的顺序,作为字母 az 的一个排列(即先输出修改后字母表中的第一个字母,然后是第二个,依此类推)。

否则输出一个单词 Impossible(不带引号)。

样例

样例 1

输入:

3
rivest
shamir
adleman

输出:

bcdefghijklmnopqrsatuvwxyz

样例 2

输入:

10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer

输出:

Impossible

样例 3

输入:

10
petr
egor
endagorion
feferivan
ilovetanyaromanova
kostka
dmitriyh
maratsnowbear
bredorjaguarturnik
cgyforever

输出:

aghjlnopefikdmbcqrstuvwxyz

样例 4

输入:

7
car
care
careful
carefully
becarefuldontforgetsomething
otherwiseyouwillbehacked
goodluck

输出:

acbdefhijklmnogpqrstuvwxyz

在线编程 IDE

建议全屏模式获得最佳体验