传送门
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int maxn = 5e5 + 10;
6 const int maxsize = 27;
7
8 int par[maxn];
9 int rnk[maxn];
10 char s1[20], s2[20];
11 int vis[maxn];
12 int ch[maxn][maxsize];
13 int val[maxn];
14
15 int t;
16
17 void init() {
18 for (int i = 0; i < maxn; i++) {
19 par[i] = i;
20 rnk[i] = 0;
21 }
22 }
23
24 int find(int x) {
25 if (par[x] == x) return x;
26 else return par[x] = find(par[x]);
27 }
28
29 void unite(int x, int y) {
30 x = find(x);
31 y = find(y);
32 if (x == y) return;
33
34 if (rnk[x] < rnk[y]) {
35 par[x] = y;
36 } else {
37 par[y] = x;
38 if (rnk[x] == rnk[y]) rnk[x]++;
39 }
40 }
41
42 bool same(int x, int y) {
43 return find(x) == find(y);
44 }
45
46 struct Tire {
47 int sz;
48 Tire() {
49 sz = 1;
50 memset(ch[0], 0, sizeof(ch[0]));
51 }
52 int idx(char c) {return c - 'a';}
53
54 int FFF(char* s) {
55 int len = strlen(s);
56 int u = 0;
57 for (int i = 0; i < len; i++) {
58 int c = idx(s[i]);
59 if (!ch[u][c]) {
60 memset(ch[sz], 0, sizeof(ch[sz]));
61 val[sz] = 0;
62 ch[u][c] = sz++;
63 }
64 u = ch[u][c];
65 }
66 if (!val[u]) val[u] = t++;
67 return val[u];
68 }
69
70 };
71
72
73
74 int main() {
75 init();
76 int tag = 0;
77 Tire Tree;
78 t = 1;
79 while (~scanf("%s%s", s1, s2)) {
80 int a = Tree.FFF(s1), b = Tree.FFF(s2);
81 vis[a]++; vis[b]++;
82 if (!same(a, b)) {
83 unite(a, b);
84 }
85 tag++;
86 //if (tag == 5) break;
87 }
88 int odd = 0;
89 bool flag = 1;
90 for (int i = 1; i < t && flag; i++) {
91 if (vis[i] & 1) odd++;
92 if (find(i) != find(1)) flag = 0;
93 }
94 if (odd != 0 && odd != 2) {
95 flag = 0;
96 }
97 if (flag) {
98 puts("Possible");
99 } else {
100 puts("Impossible");
101 }
102 return 0;
103 }