Time Limit: 5000MS		Memory Limit: 128000K
Total Submissions: 36032		Accepted: 9427

Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input

blue redred violetcyan blueblue magentamagenta cyan

Sample Output

Possible

Hint

Huge input,scanf is recommended.

Source

 

1 /*by SilverN*/ 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 const int mxn=2400;10 const int mxm=250010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}15 return x*f;16 }17 int id=0;18 struct trie{19 int a[mxn][26];20 int end[mxn];21 int cnt;22 int hash(char s[]){23 int len=strlen(s);24 int now=1;25 for(int i=0;i
            
             2)flag=0;60 else{61 int x=find(1);62 for(i=2;i<=id;i++){63 int y=find(i);64 if(x!=y){65 flag=0;66 break;67 }68 }69 }70 if(flag)printf("Possible\n");71 else printf("Impossible\n");72 return 0;73 }