Alien Dictionary Order

You are given a list of words sorted according to the lexicographical order of an unknown alien language. Your task is to determine the order of characters in this alien alphabet.

Formally, given a list of strings words, where the words are sorted based on the rules of the alien language, find a string that represents the characters in the correct order. If the ordering is invalid (e.g. a prefix appears later than a word), output an empty string.

This problem can be modeled using a graph where each unique character is a node. A directed edge from character \(u\) to \(v\) indicates that \(u\) comes before \(v\) in the language. A valid ordering is obtained by performing a topological sort on this graph.

inputFormat

The first line of input contains a single integer \(n\) which indicates the number of words. Each of the following \(n\) lines contains a word comprised of lowercase English letters.

For example:

5
wrt
wrf
er
ett
rftt

outputFormat

Output a single line containing a string that represents the order of characters in the alien language. If no valid ordering exists, print an empty string.

5
wrt
wrf
er
ett
rftt

wertf