题意：给出很多很多很多很多个棒子 左右各有颜色（给出的是单词） 相同颜色的可以接在一起，问是否存在一种
方法可以使得所以棒子连在一起
思路:就是一个判欧拉通路的题目，欧拉通路存在:没奇度顶点 或者只有2个奇度顶点 同时要连通 。关键在于给颜色hash和
判断连通性 hash用字典树 连通用并查集
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=+;
struct Trie{
int ch[maxn][];
int size;
int num[maxn];
int number;
void init(){
memset(ch,,sizeof(ch));
size=;
number=;
memset(num,,sizeof(num));
}
void insert(char*s){
int rc=,i=;
for(;s[i]!='\0';i++){
int id=s[i]-'a';
if(ch[rc][id]==){
ch[rc][id]=size++;
}
rc=ch[rc][id];
}
if(num[rc]==)num[rc]=number++;
}
int find(char*s){
int rc=,i=;
for(;s[i]!='\0';i++){
int id=s[i]-'a';
if(ch[rc][id]==){
return -;
}
// if(s[i+1]=='\0')return ch[rc][id];
rc=ch[rc][id];
}
return num[rc];
}
}trie;
int father[maxn];
int Find(int x){
return father[x]=father[x]==x?x:Find(father[x]);
}
void merge(int x,int y){
x=Find(x);
y=Find(y);
if(x!=y)
father[x]=y;
}
char s1[],s2[];
int dgree[maxn];
int main(){
trie.init();
int flag=;
for(int i=;i<=maxn;i++)father[i]=i;
int maxnum=;
while(scanf("%s%s",s1,s2)==){
trie.insert(s1);trie.insert(s2);
int x=trie.find(s1);
int y=trie.find(s2);
dgree[x]++;
dgree[y]++;
maxnum=max(maxnum,x);
maxnum=max(maxnum,y);
merge(x,y);
}
int z=;
for(int i=;i<=maxnum;i++){
if(dgree[i]%)z++;
}
flag=Find();
int ok=;
for(int i=;i<=maxnum;i++){
if(flag!=Find(i)){
// cout<<i<<" "<<Find(i)<<" "<<flag<<endl;
ok=;break;
}
}
// cout<<ok<<" "<<z<<endl;
if((ok)&&(z==||z==))printf("Possible\n");
else printf("Impossible"); return ;
}