1 /* 2    题意：将两端涂有颜色的木棒连在一起，并且连接处的颜色相同！ 3    思路：将每一个单词看成一个节点，建立节点之间的无向图！判断是否是欧拉回路或者是欧拉路 4     5    并查集判通 + 奇度节点个数等于2或者0  6 */ 7 #include<cstring> 8 #include<cstdio> 9 #include<algorithm>10 #define N 2500005*211 using namespace std;12 13 int f[N];14 int trie[N][26];15 int rank[N];16 int deg[N]; 17 18 int getFather(int x){19    return x==f[x] ? x : f[x]=getFather(f[x]);20 } 21 22 void Union(int a, int b){23     int fa=getFather(a), fb=getFather(b);24     if(fa!=fb){25         if(rank[fa]>rank[fb]){26            rank[fa]+=rank[fb]+1; 27            f[fb]=fa;28         }29         else{30             f[fa]=fb;31             rank[fb]+=rank[fa]+1;32         }33     }34 } 35 36 int main(){37    int cnt=0, c=0, cur=0;38    int u, v;39    char ch[15];40    for(int i=1; i<N; ++i)41       f[i]=i;42    while(scanf("%s", ch)!=EOF){43        ++c;44        cur=0;45        for(int i=0; ch[i]; ++i){46            if(!trie[cur][ch[i]-‘a‘])47               trie[cur][ch[i]-‘a‘]=++cnt;48            cur=trie[cur][ch[i]-‘a‘];49        }50        if(c&1)  u=cur;51        else v=cur;52        53        if((c&1)==0){54           Union(u, v); 55           ++deg[u];56           ++deg[v];57       }58    }59    int rootN=0, degN=0;60    for(int i=1; i<=cnt; ++i){61          if(deg[i] && f[i]==i) ++rootN;62          if(deg[i]&1) ++degN;63          if(rootN>1 || degN>2) break;64    }65    if(rootN==1 && (degN==0 || degN==2) || rootN==0 && degN==0)66        printf("Possible\n");67    else printf("Impossible\n");68    return 0;69 }