Hacky Ordering

시간 제한2초메모리 제한1024 MB

요약

문자열 목록이 주어질 때, 26개 알파벳의 어떤 순서로 정렬하면 목록이 정렬되는지 판별하고 그러한 순서 하나를 출력한다.

난이도: 보통10점 중 7점
유형: 그래프, 위상 정렬, 문자열, 그리디
정답자: 아직 제출이 없습니다

문제

You have been asked to sort! Again! For the bazillionth time! Not even numbers, but strings! Ugh! Do people still not have this in their standard library? Why do you even need to learn this? Who even uses a language without sort function‽

Clearly, you have not been paying attention in class for such a stupid ubiquitous function, but now you have been asked to implement it! Without calling sort! But you just cannot!

But wait! You have a better approach: what if you just assume that the list is sorted already? The order of the characters in the alphabet is arbitrary anyway\ldots{} So, instead of sorting the list, you want to determine whether there exists some order of the characters of the alphabet such that the list of strings is sorted according to this order.

Note that when a string is a prefix of some longer string, the shorter string should be sorted before the longer string.

입력

The input consists of:

One line with an integer $n$ ( $1\leq n\leq 10^5$ ), the number of strings.
$n$ lines, each with a string.

The strings only consist of English lowercase letters (a-z).

The total number of characters in the $n$ strings is at most $10^5$ .

The strings are not necessarily distinct.

출력

If it is impossible to determine an order of the alphabet, output "impossible".

If it is possible, output a permutation of the 26 letters of the English alphabet according to which the strings are sorted.

If there are multiple valid solutions, you may output any one of them.

예제4

예제 1

입력

7
c
cplusplus
csharp
python
php
java
javascript

예상 출력

cpsyhjabdefgiklmnoqrtuvwxz

예제 2
입력
```
4
aa
ba
ab
bb
```
예상 출력
```
impossible
```

예제 3

입력

5
yyy
yyyy
z
xx
xx

예상 출력

qwertyuiopasdfghjklzxcvbnm

예제 4
입력
```
2
aa
a
```
예상 출력
```
impossible
```