1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 2000 5 using namespace std; 6  7 char s1[maxn],s2[maxn]; 8 int t,m; 9 int dp[maxn][maxn];10 int g[maxn][maxn];11 12 int main()13 {14     scanf("%d",&t);15     for(int cas=1; cas<=t; cas++)16     {17         scanf("%s",s1+1);18         scanf("%s",s2+1);19         scanf("%d",&m);20         getchar();21         memset(g,0,sizeof(g));22         for(int i=1; i<=m; i++)23         {24             char ch1,ch2;25             scanf("%c %c",&ch1,&ch2);26             getchar();27             g[ch2-‘a‘][ch1-‘a‘]=1;28         }29         memset(dp,0,sizeof(dp));30         int k1=strlen(s1+1);31         int k2=strlen(s2+1);32         bool flag=true;33         for(int i=1; i<=k1; i++)34         {35             for(int j=1; j<=k2; j++)36             {37                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);38                 if(s1[i]==s2[j]||(g[s1[i]-‘a‘][s2[j]-‘a‘]==1))39                 {40                     dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);41                 }42             }43         }44         printf("Case #%d: ",cas);45         if(dp[k1][k2]==k1) printf("happy\n");46         else printf("unhappy\n");47     }48     return 0;49 }