Description
在一种未知语言中，很多单词被发现了，但是他们的字母的字典序我们是不知道的。我们知道的是，这些单词是按照字典序从小到大排列的。
或者找出这种语言唯一的字母的字典序，或者得出这种方案是不存在的，或者得出有很多种这样的方案。
Input
第一行包括一个正整数n(1≤n≤100)，表明单词的数量。
接下来n行，每行一个单词，每个单词最多包含10个小写的英文字母。保证单词以未知语言的字典序给出。
Output
有且仅有一行，输出包含所有字母的字典序。如果没有这种字典序，则输出“!”，如果有多种方案则输出“?”。（多解与无解先判多解情况）
Samples
Input Copy
5
ula
uka
klua
kula
al
Output
luka
Input Copy
3
marko
darko
zarko
Output
?
Hint
【数据范围与约定】
对于30%的数据：n≤20。
对于100%的数据：n≤100。
思路：
相当于是一种传递关系，如果a的字典序大于b的字典序，b的字典序大于c的字典序，那么a的字典序一定大于c的字典序。可以用floyd来传递这种关系。
g[i][j]表示i的字典序小于j的字典序。
先考虑一下无解和多种解的情况：
以下要先保证i和j都出现过
1.无解：当g[i][j]和g[j][i]均为1时，说明i的字典序大于j的字典序，j的字典序也大于i的字典序，两种情况是矛盾的，无解。
2.多解：当g[i][j]和g[j][i]均为0时，说明两者的大小关系无法确定，多解。
3.唯一解如何输出答案：排除以上两种情况，就是唯一解的情况了。根据g数组的含义，我们可以计算出比i的字典序大的字母有多少个，按顺序输出就好了。
代码：
int g[27][27];
string s[110];
map<int,int>mp;
int res[27];
int cnt=0;
int main()
{
int n=read();
for(int i=1; i<=n; i++)
cin>>s[i];
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
int minn=min(s[i].size(),s[j].size());
for(int k=0; k<minn; k++)
{
if(s[i][k]==s[j][k]) continue;
g[s[i][k]-'a'+1][s[j][k]-'a'+1]=1;
break;
}
for(int k=0; k<s[i].size(); k++) mp[s[i][k]-'a'+1]=1;
for(int k=0; k<s[j].size(); k++) mp[s[j][k]-'a'+1]=1;
}
}
for(int k=1; k<=26; k++)
for(int i=1; i<=26; i++)
for(int j=1; j<=26; j++)
g[i][j]|=g[i][k]&g[k][j];
for(int i=1; i<=26; i++)
{
if(mp[i]) ///该数字出现过
{
int tmp=0;
cnt++;
for(int j=1; j<=26; j++)
{
if(mp[j]&&i!=j)
{
if(g[i][j]&&!g[j][i]) tmp++;
else if(!g[i][j]&&!g[j][i])
{
puts("?");
return ;
}
else if(g[i][j]&&g[j][i])
{
puts("!");
return ;
}
}
}
res[tmp]=i;
}
}
for(int i=cnt-1; i>=0; i--) printf("%c",res[i]-1+'a');
return 0;
}