題目大意：給定一些木棒，木棒兩端都涂上顏色，求是否能將木棒首尾相接，連成一條直線，要求不同木棒相接的一邊必須是相同顏色的。

我們把顏色看做點，木棒看做邊，這道題就轉為了求是否存在歐拉路。

而判斷歐拉路只要看兩點 ①圖連通 ②所有節點的度為偶數或只有兩個奇數度節點。

判斷①我們可以使用并查集且必須壓縮路徑，否則會超時。而并查集需要利用數組下標，但讀入為字符串，并且有25w條邊，使用hash會超時。

這時候我們可以用trie（字典樹），關于字典樹可以自行百度。

#include <cstdio>#include <iostream>#include <cstring>#define maxn 500000using namespace std;struct Trie{	Trie* next[27];	bool flag;	int id;	Trie()    {        flag=false;        id=0;        memset(next,0,sizeof(next));    } }root;int tot;int dg[maxn+5];int fa[maxn+5];int trie(char *ch){	Trie* tree=&root;	int len=0;	while (ch[len]!='/0')	{		int pub=ch[len++]-'a';		if (!tree->next[pub]) tree->next[pub]=new Trie();		tree=tree->next[pub];	}	if (tree->flag) return tree->id;	else 	{		tree->flag=true;		tree->id=++tot;		return tree->id=tot;	}}int getf(int x){	if (fa[x]!=x) fa[x]=getf(fa[x]);	return fa[x];}void ice_chair(int x,int y){	int fx=getf(y);	int fy=getf(x);	fa[fy]=fx;	return ;}char a[15],b[15];int main(){	register int i,j;	for (i=1;i<=maxn;i++)	{		fa[i]=i;	}	while(cin>>a>>b)	{		int x=trie(a);		int y=trie(b);		dg[x]++;		dg[y]++;		ice_chair(x,y);	}	int s=getf(1);	int ans=0;	for (i=1;i<=tot;i++)	{		if (dg[i]%2==1) ans++;		if (ans>2)		{			PRintf("Impossible");			return 0;		}		if (getf(i)!=s)		{			printf("Impossible");			return 0;			}	}	if (ans==1) printf("Impossible");	else printf("Possible");	return 0;}