Codeforces 510C

#include <iostream>

#include <vector>

using namespace std;

string ret;

vector<vector<int>> adj(27);

bool dfs(int node,vector<bool>& vu,vector<bool>& path){

if (path[node]) return false;

if (vu[node]) return true;

vu[node]=true;

path[node]=true;

ret += 'a'+node;

for (auto& i:adj[node]){

if (!dfs(i,vu,path)) return false;

}

path[node]=false;

return true;

}

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n;

cin >> n;

vector<string> v(n);

for (int i=0; i<n; ++i) cin >> v[i];

vector<vector<int>> adj(27);

for (int i=0; i<n-1; ++i){

string target=v[i],source=v[i+1];

if (target.size() > source.size() and target.substr(source.size()-1) == source){

cout << "Impossible";

return 0;

}

int idx=0;

while (idx < target.size() and target[idx] == source[idx]) idx++;

if (idx == target.size()) continue;

adj[source[idx]-'a'].emplace_back(target[idx]-'a');

}

vector<bool> vu(27),path(27); 

for (int i=0; i<26; ++i){

bool ok=true;

if (!vu[i]) ok=dfs(i,vu,path);

if (!ok){

cout << "Impossible";

return 0;

}

}

for (int i=0; i<26; ++i){

if (!vu[i]) ret += i+'a';

}

cout << ret;

return 0;

}