//Accepted    4372 KB    140 ms
 //dp 最长上升子序列 nlogn
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 using namespace std;
 ;
 int dp[imax_n];
 int d[imax_n];
 int a[imax_n];
 int n;
 int len;
 int max(int a,int b)
 {
     return a>b?a:b;
 }
 int binary_search(int k)
 {
     ;
     int r=len;
     while (l<=r)
     {
         ;
         if (d[mid]==k) return mid;
         ;
         ;
     }
     return l;
 }
 void Dp()
 {
     memset(dp,,sizeof(dp));
     memset(d,,sizeof(d));
     len=-;
     ;i<n;i++)
     {
         int j=binary_search(a[i]);
         //printf("j=%d\n",j);
         if (j>len) len++;
         dp[i]=j+;
         d[j]=a[i];
     }
     ;
     ;i<n;i++)
     ans=max(ans,dp[i]);
     )
     {
         printf("My king, at most 1 road can be built.\n");
     }
     else
     {
         printf("My king, at most %d roads can be built.\n",ans);
     }
 }
 int main()
 {
     ;
     while (scanf("%d",&n)!=EOF)
     {
         int x,y;
         ;i<n;i++)
         {
             scanf("%d%d",&x,&y);
             a[x-]=y;
         }
         printf("Case %d:\n",++t);
         Dp();
         printf("\n");
     }
     ;
 }