瑞瑞的木棍(Colored Sticks)

瑞瑞有一堆的玩具木棍，每根木棍的两端分别被染上了某种颜色，现在他突然有了一个想法，想要把这些木棍连在一起拼成一条线，并且使得木棍与木棍相接触的两端颜色都是相同的，给出每根木棍两端的颜色，请问是否存在满足要求的排列方式。

例如，如果只有 $2$ 根木棍，第一根两端的颜色分别为 red 和 blue，第二根两端的颜色分别为 red 和 yellow，那么 blue --- red | red --- yellow 便是一种满足要求的排列方式。

输入有若干行，每行包括两个单词，表示一根木棍两端的颜色，单词由小写字母组成，且单词长度不会超过 $10$ 个字母，最多有 $250000$ 根木棍。

如果木棒能够按要求排列，输出 Possible，否则输出 Impossible。

blue red
red violet
cyan blue
blue magenta
magenta cyan

Possible

对于 $100\%$ 的数据，单词长度不超过 $10$ 个小写字母，木棍数量不超过 $2.5 \times 10^5$ 。

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~7	小规模 m≤20 / 特殊: m=1单根木棍 / 特殊: 两个分离欧拉环不连通输出Impossible
2	20	8~13	中等规模 m≤10000 / Hack: 连通但恰有4个奇度颜色输出Impossible
3	30	14~20	满规模 m=250000,50万颜色词 128MB内存限制下哈希+并查集欧拉路判定
4	20	21~25	满规模 m=250000 10字母长词欧拉路径/回路/无解综合回归

出处：原题链接

#P1333. 瑞瑞的木棍(Colored Sticks)