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; }
