PTA l3-031 thousand hand Guanyin (30 points)

PTA L3-031 Thousand-hand Bodhisattva (30 branch )

Humans like to use 10 Base number , Probably because humans have two hands 10 A finger is used to count . So in the world of thousand hand Guanyin , The numbers are 10 000 It's binary , Because every Guanyin has 1 000 Both hands ……

Each finger of thousand hand Guanyin corresponds to a symbol （ But the symbols in Guanyin world are too difficult to draw , Let's use a string of lowercase English letters to represent ）, It's like humans use their own 10 Root finger correspondence 0 To 9 this 10 A digital . alike , Just like humans put this 10 A number arranged to represent a larger number ,ta They also put these names together to represent larger numbers , And also follow the rules of high on the left and low on the right , Use a dot between adjacent names . Separate , for example pat.pta.cn It means one in the thousand hand Guanyin world 3 digit .

Humans do not know the size of the numbers represented by these symbols . But fortunately , Humans have discovered a string of numbers left by thousand handed Guanyin , And have reason to believe , This string of numbers is ordered from small to large ！ So your task came ： Please according to this series of orderly numbers , The relative order of symbols represented by each hand of thousand hand Guanyin is deduced .

Be careful ： It may not be possible to get the full order from this string of numbers , You just try to get the results you can get . When the relative order between several fingers cannot be determined , Let's arrange them in ascending order according to their English dictionaries . For example, given the following numbers ：

pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat

We can first infer from the first two numbers pat < cn; According to the order of the high order on the left, we can infer lao < pta < cn; Then, according to the order of the low order when the high order is equal , It can be inferred that cn < oms,lao < pat. To sum up, we get two possible orders ：lao < pat < pta < cn < oms; perhaps lao < pta < pat < cn < oms, namely pat and pta The relative order between cannot be determined , At this time, we arrange them in dictionary order , obtain lao < pat < pta < cn < oms.

Input format ：
The first line of input gives a positive integer $N(\le 10^5)$, The number of numbers left for thousand hand Guanyin . And then N That's ok , Each line gives a number left by thousand hand Guanyin , No more than 10 digit , The symbol of each bit shall not exceed 3 A lowercase letter indicates , Use... Between two adjacent symbols . Separate .

We assume that the numerical order given is strictly increasing in the world of thousand hand Guanyin . The title guarantee number is $10^4$ It's binary , That is, the types of symbols must not exceed $10^4$ Kind of .

Output format ：
Output symbols in ascending order in a row . When the relative order between several fingers cannot be determined , In ascending order of their English dictionaries . Between symbols still use . Separate .

sample input ：

7
pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat

sample output ：

lao.pat.pta.cn.oms

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

unordered_map<string,int> d;
unordered_map<string,vector<string>> g;

vector<string> get(string str)
{
    
	vector<string> res;
	string word;
	for(auto &c:str)
	{
    
		if(c=='.')
		{
    
			res.push_back(word);
			if(!d.count(word)) d[word]=0;
			word="";
		}
		else word+=c;
	}
	res.push_back(word);
	if(!d.count(word)) d[word]=0;
	return res;
}

vector<string> topsort()
{
    
	priority_queue<string,vector<string>,greater<string>> Q;
	for(auto &[k,v]:d) 
		if(!v)
			Q.push(k);
	
	vector<string> res;
	while(!Q.empty())
	{
    
		string t=Q.top();Q.pop();
		res.push_back(t);
		for(auto &p:g[t])
			if(--d[p]==0)
				Q.push(p);
	}
	return res;
}

int main()
{
    
	ios::sync_with_stdio(false);
	
	int n;cin>>n;
	string str;cin>>str;
	vector<string> last=get(str);
	
	for(int i=0;i<n-1;i++)
	{
    
		cin>>str;
		vector<string> cur=get(str);
		if(last.size()==cur.size())
		{
    
			for(int j=0;j<(int)cur.size();j++)
				if(last[j]!=cur[j])
				{
    
					g[last[j]].push_back(cur[j]);
					d[cur[j]]++;
					break;
				}
		}
		last=cur;
	}
	
	vector<string> res=topsort();
	cout<<res[0];
	for(int i=1;i<(int)res.size();i++)
		cout<<"."<<res[i];
	return 0;
}