思路:把每根筷子的两个端点的字符串看成一个点，建图，问题即转化为判断图是否是含有欧拉通路，满足两个条件：
（1）图是连通图，（2）奇数度的点个数要么是0，要么是2。
无向图判断是否连通很简单，并查集直接搞就行，最后看是不是只有一个连通分量。
建图时把每个字符串转化为一个整数，这样才好建图，第一反应是用map，交了一发TLE，然后干脆直接用trie树吧，1000+ms过的，有点慢。
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 250010;
typedef struct Node{
int cnt;
Node *child[26];
Node(){
cnt = 0;
for(int i = 0;i < 26;i ++)
child[i] = NULL;
}
}Node;
Node* root;
int father[(MAXN << 1)+10],ind[(MAXN << 1)+10],n;
inline int update(char* str){
Node *tmp = root;
while(*str != ' '){
if(tmp->child[*str-'a'] == NULL){
Node *p = new Node();
tmp->child[*str-'a'] = p;
}
tmp = tmp->child[*str-'a'];
str++;
}
if(tmp->cnt == 0) tmp->cnt = ++n;
return tmp->cnt;
}
inline void init(){
n = 0,root = new Node();
memset(ind,0,sizeof ind);
for(int i = 1;i <= MAXN*2;i ++)
father[i] = i;
}
int find(int x){
return x == father[x] ? x : father[x] = find(father[x]);
}
inline void merge(int x,int y){
x = find(x);
y = find(y);
father[y] = x;
}
int main(){
init();
int x,y;
char str1[20],str2[20];
#ifndef ONLINE_JUDGE
freopen("in.cpp","r",stdin);
#endif
while(~scanf("%s%s",str1,str2)){
x = update(str1),y = update(str2);
if(find(x) != find(y)) merge(x,y);
ind[x]++,ind[y]++;
}
int sum = 0;
for(int i = 1;i <= n;i ++){
if(i == find(i)) sum ++;
if(sum > 1){
printf("Impossible
");
return 0;
}
}
sum = 0;
for(int i = 1;i <= n;i ++){
if(ind[i]&1) sum ++;
if(sum > 2){
printf("Impossible
");
return 0;
}
}
printf("Possible
");
return 0;
}