这题用map就超时了，所以用字典树来优化，第一次写静态的，现在都不习惯用指针了。
由于这里不要回到源点，所以不许要所有点的度都为偶数，零个或者两个均可，图也必须是连通的。
代码如下：
#include <cstring> #include <cstdlib> #include <cstdio> #include <string> using namespace std;char s1[15], s2[15]; int idx = 0, flag = 0, ptr = 1;int set[2500005];struct Node {int cnt, No;int ch[26]; }e[1250005];int find(int x) {return set[x] = x == set[x] ? x : find(set[x]); }int insert(int p, char *in) {if (*in == '\0') {if (e[p].cnt == 0) {e[p].No = ptr++;}++e[p].cnt;if (e[p].cnt & 1) {++flag;}else {--flag;}return find(e[p].No);}else {if (e[p].ch[*in-'a'] == 0) {++idx;e[p].ch[*in-'a'] = idx;}insert(e[p].ch[*in-'a'], in+1);} }int main() {int x, y, root = 0;for (int i = 0; i <= 2500000; ++i) {set[i] = i;}while (scanf("%s %s", s1, s2) == 2) {x = insert(0, s1);y = insert(0, s2);if (x != y) {set[x] = y;}}for (int i = 1; i < ptr; ++i) {if (set[i] == i) {++root;}}if (ptr == 1 || (flag == 0 || flag == 2) && root == 1) {puts("Possible");}else {puts("Impossible");}return 0; }