题目的实质是要判断图中是否存在欧拉通路。所谓欧拉通路，是指一个图中，走过每个边一次且仅一次的一条路径。若一个无向图中存在欧拉通路，当且仅当（1）只有两个节点的度数为奇数（2）图是连通的。对于这个题目，色数未知，即节点数未知，但很明显，节点数<=木棒个数*2，所以设节点上限为500000。用并查集判断图的连通情况，用trie树统计颜色（即节点）个数，然后利用定理即可AC。
下面给出源代码，由于是看了某位大牛的解题报告才做出来的，所以代码有些相似- -，只怪自己太水了，不会trie树，这么水的题都 不会做。。。555555555，不过现在会了 哈哈哈哈
#include <iostream>
#define max 500001
using namespace std;
struct node
{
int flag;
node *p[26];
node()
{
int i;
flag=-1;
for(i=0;i<26;i++)
p[i]=NULL;
}
}root;
int sum,rank[max],f[max],d[max];
char s1[10],s2[10];
int getnum(char *s)
{
int i;
node *r=&root;
for(i=0;s[i];i++)
{
if(r->p[s[i]-'a']==NULL)
r->p[s[i]-'a']=new node();
r=r->p[s[i]-'a'];
}
if(r->flag==-1)
r->flag=sum++;
return r->flag;
}
int father(int i)
{
if(f[i]!=i)
f[i]=father(f[i]);
return f[i];
}
void Union(int i,int j)
{
i=father(i);
j=father(j);
if(i==j)
return;
if(rank[i]>rank[j])
f[j]=i;
else
{
f[i]=j;
if(rank[i]==rank[j])
rank[j]++;
}
}
int main()
{
int i,j,k;
sum=0;
memset(rank,0,sizeof(rank));
memset(d,0,sizeof(d));
for(i=0;i<max;i++)
f[i]=i;
while(scanf("%s%s",&s1,&s2)!=EOF)
{
i=getnum(s1);
j=getnum(s2);
d[i]++;
d[j]++;
if(i!=j)
Union(i,j);
}
for(i=0,k=0;i<sum;i++)
if(d[i]%2)
k++;
j=father(0);
for(i=1;i<sum;i++)
if(father(i)!=j)
{
printf("Impossible/n") ;
return 0;
}
if(k<3)
printf("Possible/n");
else
printf("Impossible/n");
return 0;
}