#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int imax_n = 2500005;struct Trie{ int a[26]; int isEnd;}f[imax_n];int e;void init1(){ e=1; f[0].isEnd=0; memset(f[0].a,-1,sizeof(f[0].a));}int add(char *s){ int i=0; int t=0; while (s[i]) { if (f[t].a[s[i]-'a']==-1) { f[t].a[s[i]-'a']=e++; t=f[t].a[s[i]-'a']; f[t].isEnd=0; memset(f[t].a,-1,sizeof(f[t].a)); } else t=f[t].a[s[i]-'a']; i++; } f[t].isEnd++; return t;}int search(char *s){ int i=0; int t=0; while (s[i] && f[t].a[s[i]-'a']!=-1) { t=f[t].a[s[i]-'a']; i++; } if (!s[i]) return -1; if (f[t].isEnd!=0) return -1; return t;}int father[imax_n];void init2(){ for (int i=0;i<2500005;i++) father[i]=i;}int find(int x){ if (father[x]==x) return x; return father[x]=find(father[x]);}void union_set(int x,int y){ int fx=find(x); int fy=find(y); if (fx!=fy) { father[fx]=fy; }}char s1[15];char s2[15];int count[imax_n];int main(){ init1(); init2(); memset(count,0,sizeof(count)); int a,b; while (scanf("%s%s",s1,s2)!=-1) { a=add(s1); //printf("add s1n"); count[a]++; b=add(s2); count[b]++; union_set(a,b); } int ans=0; for (int i=0;i<e;i++) { //if (count[i]!=0) printf("count[%d]=%dn",i,count[i]); ans+=count[i]%2; } if (!(ans==0 || ans==2)) { printf("Impossiblen"); return 0; } ans=0; for (int i=0;i<e;i++) if (count[i]!=0) ans+=(father[i]==i); if (ans>1) { printf("Impossiblen"); } else { printf("Possiblen"); } return 0;}
