#K42507. Alien Dictionary Order
Alien Dictionary Order
Alien Dictionary Order
In this problem, you are given a sequence of words sorted lexicographically according to an unknown (alien) alphabet. Your task is to deduce the correct order of the characters in this alien alphabet.
Formally, let (\mathcal{A}) be the set of characters used by the alien language. The ordering must satisfy that for every directed edge (u \to v) in the precedence graph (derived from adjacent words), the position of (u) is less than the position of (v):
[ \forall (u \to v), \ \text{pos}(u) < \text{pos}(v) ]
If the order cannot be determined (either due to a cycle or because a word is a prefix of a previous word), output Impossible
.
inputFormat
The input is read from standard input. The first line contains an integer (n) representing the number of words. This is followed by (n) lines, each containing a non-empty string which is a word in the alien language.
outputFormat
Output to standard output a single line containing a string that represents the ordered sequence of characters according to the alien alphabet. If it is impossible to determine such an order, output Impossible
.## sample
5
wrt
wrf
er
ett
rftt
wertf