You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
1.3 KiB
64 lines
1.3 KiB
#include <iostream>
|
|
#include <cstdio>
|
|
#include <algorithm>
|
|
#include <map>
|
|
#include <cstring>
|
|
using namespace std;
|
|
typedef unsigned long long ULL;
|
|
const int N = 250010 << 1;
|
|
int p[N];
|
|
int d[N];
|
|
|
|
ULL getHash(string s) {
|
|
int P = 131, b = 1;
|
|
ULL hash = 0;
|
|
for (int i = 0; i < s.size(); i++) {
|
|
hash = hash + s[i] * b;
|
|
b = b * P;
|
|
}
|
|
return hash;
|
|
}
|
|
|
|
int find(int x) {
|
|
if (x == p[x]) return x;
|
|
return p[x] = find(p[x]);
|
|
}
|
|
|
|
char str1[15], str2[15];
|
|
int b[N];
|
|
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("POJ2513.in", "r", stdin);
|
|
#endif
|
|
|
|
for (int i = 0; i < N; i++) p[i] = i;
|
|
|
|
int n = 0, flag = 1;
|
|
|
|
while (~scanf("%s%s", str1, str2)) {
|
|
int s1 = getHash(str1) % N, s2 = getHash(str2) % N;
|
|
if (!b[s1]) b[s1] = ++n;
|
|
if (!b[s2]) b[s2] = ++n;
|
|
int x = b[s1], y = b[s2];
|
|
d[x]++, d[y]++;
|
|
|
|
if (find(x) != find(y)) p[find(x)] = find(y);
|
|
}
|
|
|
|
int odd = 0, cnt = 0;
|
|
for (int i = 1; i <= n; i++) {
|
|
if (p[i] == i) cnt++;
|
|
if (d[i] % 2) odd++;
|
|
}
|
|
|
|
if ((odd != 0 && odd != 2) || cnt != 1) flag = 0;
|
|
|
|
if (n == 0) flag = 1;
|
|
|
|
if (flag)
|
|
puts("Possible");
|
|
else
|
|
puts("Impossible");
|
|
return 0;
|
|
} |