7月21日备战Noip2017暑假集训6(A) 单词 【拓扑排序】

单词

【问题描述】

在一种未知语言中,很多单词被发现了,但是他们的字母的字典序我们是不知道的。我们知道的是,这些单词是按照字典序从小到大排列的。

或者找出这种语言唯一的字母的字典序,或者得出这种方案是不存在的,或者得出有很多种这样的方案。

【输入格式】

第一行包括一个正整数n(1 <= n <= 100),表明单词的数量。

接下来n行,每行一个单词,每个单词最多包含10个小写的英文字母。保证单词以未知语言的字典序给出。

【输出格式】

有且仅有一行,输出包含所有字母的字典序。如果没有这种字典序,则输出“!”,如果有多种方案则输出“?”。

【输入样例1

5

ula

uka

klua

kula

al

【输出样例1

luka

【输入样例2

4

jaja

baba

baja

beba

【输出样例2

【输入样例3

3

marko

darko

zarko

【输出样例3

数据范围与约定

对于30%的数据:n <= 20。

对于100%的数据:n <= 100。

继续阅读7月21日备战Noip2017暑假集训6(A) 单词 【拓扑排序】