510C.md (2460B)
1 Source: https://codeforces.com/problemset/problem/510/C 2 3 C. Fox And Names 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order. 22 23 After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical! 24 25 She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order. 26 27 Lexicographical order is defined in following way. When we compare *s* and *t*, first we find the leftmost position with differing characters: *s**i* ≠ *t**i*. If there is no such position (i. e. *s* is a prefix of *t* or vice versa) the shortest string is less. Otherwise, we compare characters *s**i* and *t**i* according to their order in alphabet. 28 29 Input 30 31 The first line contains an integer *n* (1 ≤ *n* ≤ 100): number of names. 32 33 Each of the following *n* lines contain one string *name**i* (1 ≤ |*name**i*| ≤ 100), the *i*-th name. Each name contains only lowercase Latin letters. All names are different. 34 35 Output 36 37 If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on). 38 39 Otherwise output a single word "Impossible" (without quotes). 40 41 Examples 42 43 Input 44 45 ``` 46 3 47 rivest 48 shamir 49 adleman 50 ``` 51 52 Output 53 54 ``` 55 bcdefghijklmnopqrsatuvwxyz 56 ``` 57 58 Input 59 60 ``` 61 10 62 tourist 63 petr 64 wjmzbmr 65 yeputons 66 vepifanov 67 scottwu 68 oooooooooooooooo 69 subscriber 70 rowdark 71 tankengineer 72 ``` 73 74 Output 75 76 ``` 77 Impossible 78 ``` 79 80 Input 81 82 ``` 83 10 84 petr 85 egor 86 endagorion 87 feferivan 88 ilovetanyaromanova 89 kostka 90 dmitriyh 91 maratsnowbear 92 bredorjaguarturnik 93 cgyforever 94 ``` 95 96 Output 97 98 ``` 99 aghjlnopefikdmbcqrstuvwxyz 100 ``` 101 102 Input 103 104 ``` 105 7 106 car 107 care 108 careful 109 carefully 110 becarefuldontforgetsomething 111 otherwiseyouwillbehacked 112 goodluck 113 ``` 114 115 Output 116 117 ``` 118 acbdefhijklmnogpqrstuvwxyz 119 ```