Codeforce Round #486 (Div.3) B. Substrings Sort

B. Substrings Sort

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String $a$ is a substring of string $b$ if it is possible to choose several consecutive letters in $b$ in such a way that they form $a$. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

Input

The first line contains an integer $n$ ($1\le n\le 100$) — the number of strings.

The next $n$ lines contain the given strings. The number of letters in each string is from $1$ to $100$, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

Output

If it is impossible to reorder $n$ given strings in required order, print "NO" (without quotes).

Otherwise print "YES" (without quotes) and $n$ given strings in required order.

Examples

input

Copy

5
a
aba
abacaba
ba
aba

output

Copy

YES
a
ba
aba
aba
abacaba

input

Copy

5
a
abacaba
ba
aba
abab

output

Copy

NO

input

Copy

3
qwerty
qwerty
qwerty

output

Copy

YES
qwerty
qwerty
qwerty

Note

In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

题意：给你一堆字符串，能不能把它们排序，排成从上到下，上面一个是下面一个的子字符串的格式，能就按格式全部输出，不能就输出“NO”.

#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){
	if(a.length()==b.length()){
		return a<b;
	}return a.length()<b.length();   //先把所有字符串排序 
}                                    //按字符串长度，字典序排序 
string a[200];
int main(){
	int m;
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>a[i];
	}
	sort(a,a+m,cmp);
	
	bool ff=true;
	for(int i=0;i<m-1;i++){                 //遍历所有 
	    bool f=true;
		int t=a[i].length();
		string temp=a[i+1];
		int tt=a[i+1].length();
		for(int j=0;j<=tt-t;j++){           
			if(temp.substr(j,t)==a[i]){    //两个两个检查，假如其中有一组(两个相邻)的，不合要求，标记 
				f=false;                  
			}
		}
		if(f){
			ff=false;         //利用标记退出； 
			break;
		}
	}
	if(!ff){
		cout<<"NO"<<endl;
	}
	else {
		cout<<"YES"<<endl;
		for(int i=0;i<m;i++){
			cout<<a[i]<<endl;
		}
	}
	return 0;
}