Colored Sticks

Time Limit: 5000MS		Memory Limit: 128000K
Total Submissions: 24844		Accepted: 6542

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

1 #include
     
        2 #include
      
         3 #include
       
          4 typedef struct node  5 {  6     int order;         //存储该颜色在对应数组中的编号  7     struct node *next[26];  8 }node;  9  10 //注意最多有250000个棒，所以最多应该有500000种颜色 11 int father[500005];   //并查集中记录父亲节点 12 int degree[500005];   //记录每个颜色出现的次数，用于欧拉路的判断 13  14 int t,k;     //t为记录标号增加的数组指针，k为静态内存分配时的数组指针 15  16 int search(char *s,node *T)         //返回s所表示的颜色在数组中的编号 17 { 18     int len,i,j,id,flag=0; 19     node *p,*q; 20     len=strlen(s); 21     p=T; 22     for(i=0;i
        
         next[id]==NULL) 26         { 27             flag=1; 28             q=(node *)malloc(sizeof(node)); 29             for(j=0;j<26;++j) 30                 q->next[j]=NULL; 31             p->next[id]=q; 32         } 33         p=p->next[id]; 34     } 35     if(flag)    //肯定是新出现的颜色---因为有新开辟的节点 36     { 37         p->order=t;         //t存储该颜色在数组中对应的编号 38         degree[t++]++;      //该颜色的度增加一 39         return p->order; 40     } 41     else 42     { 43         if(p->order==0)   //也是新颜色----因为没有颜色在此标记 44         { 45             p->order=t;         //t存储该颜色在数组中对应的编号 46             degree[t++]++;      //该颜色的度增加一 47             return p->order; 48         } 49         degree[p->order]++;      //出现过的颜色，对应的度增加一 50         return p->order; 51     } 52 } 53  54 int find_father(int i) 55 { 56     if(father[i]==-1) 57         return i; 58     else 59         return find_father(father[i]); 60 } 61  62 void merge(int num1,int num2) 63 { 64     num1=find_father(num1); 65     num2=find_father(num2); 66     if(num1!=num2) 67     { 68         if(father[num1]
         
          order=0; 86     for(i=0;i<26;++i) 87         T->next[i]=NULL; 88     while(scanf("%s%s",s1,s2)!=EOF) 89     { 90         num1=search(s1,T); 91         num2=search(s2,T); 92         merge(num1,num2); 93     } 94     for(i=1;i
          
           1) //说明不连通 98 printf("Impossible\n"); 99 else100 {101 flag=0;102 for(i=1;i