#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int MAXN = ;

 struct Node{

     int p,r;

 };

 Node a[MAXN];

 int dp[MAXN],t[MAXN];

 int len=;

 bool cmp(Node a,Node b)

 {

     if(a.p==b.p)

         return a.r<b.r;

     return a.p<b.p;

 }

 int bin_search(int key)

 {

     int low,high,mid;

     low=,high=len;

     while(low<high)

     {

         mid=(low+high)>>;

         if(t[mid]>=key)

             high=mid;

         else low=mid+;

     }

     return low;

 }

 int main()

 {

     int N;

     int cas=;

     while (scanf("%d", &N) == )

     {

         for (int i = ; i < N; i++) {

             scanf("%d%d",&a[i].p,&a[i].r);

             dp[MAXN]=INF;

         }

         sort(a,a+N,cmp);

         len=;

         t[]=a[].r;

         for(int i=;i<N;i++){

             if(a[i].r>t[len-])

                 t[len++]=a[i].r;

             else{

                 int pos=bin_search(a[i].r);

                 t[pos]=a[i].r;

             }

         }

         if(len==)

         printf("Case %d:\nMy king, at most %d road "

               "can be built.\n\n",cas++,len);

         else

         printf("Case %d:\nMy king, at most %d roads "

               "can be built.\n\n",cas++,len);

     }

     return ;

 }