这道题目是多个数据结构的集合体，考察了字典树，欧拉路，并查集。
判断一个无向图有欧拉路的标准：
1，图是联通的
2，图的各个节点的度，只有0个或者只有2个是为奇数个的。
判断图的联通：
创建并查集，如果所有的点的祖先都是同一个点的话，则为联通图。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct list
{int id;int num;struct list *next[27];
}*root;
int color;
int f[500001];
int du[500001];
int zhuang[500001];
struct list *creat()
{int i;struct list *p;p=new list;p->id=0;p->num=0;for(i=0;i<27;i++){p->next[i]=0;}return p;
}
int dos(char str[])
{struct list *p;p=root;int n,j;n=strlen(str);for(j=0;j<n;j++){int c=str[j]-'a';if(p->next[c]==NULL){p->next[c]=creat();}p=p->next[c];}if(p->num==0){p->num++;p->id=++color;}else{p->num++;}return p->id;
}
int fx(int x)
{while(x!=f[x])x=f[x];return x;
}
int pan()
{int i,x;int leap=0;memset(zhuang,0,sizeof(zhuang));for(i=1;i<=color;i++){if(zhuang[i]==0){x=i;while(x!=f[x]){zhuang[x]=1;x=f[x];}zhuang[x]=1;if(leap==0)leap=x;else{if(leap!=x)break;}}}if(i!=color+1)return 0;return 1;}
int main()
{int i,a,b;int leap=1;char str1[11],str2[11];root=creat();memset(du,0,sizeof(du));// freopen("in.txt","r",stdin);color=0;for(i=0;i<500001;i++){f[i]=i;}while(scanf("%s%s",str1,str2)!=EOF){if(str1[0]=='*')break;a=dos(str1);b=dos(str2);du[a]++;du[b]++;// printf("%d %d\n",a,b);f[fx(a)]=fx(b);}int ss;ss=0;for(i=1;i<=color;i++){if(du[i]%2==1){ss++;}}if(ss==0||ss==2)leap=1;else leap=0;//printf("~~~~~%d %d\n",ss,leap);if(!pan()){leap=0;}if(leap==1)printf("Possible\n");elseprintf("Impossible\n");return 0;
}