import java.util.*;

public class hd1025 {

    /**
     * @param args
     */
        public static void main(String[] args) {
        // TODO 自動生成方法存根
        Scanner s = new Scanner(System.in);
        int c=0;
        while (s.hasNextInt()) {
            int n=s.nextInt();
            int a[]=new int[n];
            int amax[]=new int[n];
            int len=0;
            for(int i=0;i<n;i++){
                int no=s.nextInt();
                a[no-1]=s.nextInt();   
            }
            for(int i=0;i<n;i++){
                int l=0,r=len-1;
                int m;
                while(l<=r){
                    m = (l + r)/2;
                    if(a[i] < amax[m])
                     r = m-1;
                    else
                     l = m+1;
                }
                if (l != len)
                    amax[l] = a[i];
                else
                    amax[len++] = a[i];
            }
            c++;
            System.out.println("Case"+c+":");   
            if(len==1)
                System.out.println("My king, at most "+len+" road can be built.");
            else
                System.out.println("My king, at most "+len+" roads can be built.");
            System.out.println();   
        }
         s.close();   
    }

}
//***********************************************java代碼******************************************************
#include <iostream>
using namespace std;

int a[500000],amax[500000];
int main()
{
    int n;
    int c=1;
    while(scanf("%d",&n)==1)
    { 
        int len = 0;
        for(int j=0; j<n; j++)
        {
            int no;
            scanf("%d",&no);
            scanf("%d",&a[no-1]);
        }
        for(j=0; j<n; j++)
        {   
            //二分查找
            int l=0,r=len-1;
            int ma = 0;
           
            while(l<=r)
            {
                ma = (l + r)/2;
                if(a[j] < amax[ma])
                    r = ma-1;
                else
                    l = ma+1;
            }
            if(l != len)
                amax[l] = a[j];
            else
                amax[len++]=a[j];
        }   
        printf("Case %d:\n",c++);
        if(len==1)
            printf("My king, at most %d road can be built.\n\n",len);
        else
            printf("My king, at most %d roads can be built.\n\n",len);
    }
    return 0;
}
//************************************************c++代碼********************************************************
注:本題其實就是求最長遞增子序列,采用動態規劃算法,具體上上網查找相關....
    另本題中要注意對輸入的序列排序
    在算法一樣的情況下,java代碼不能提交成功,說運行超時,C++代碼沒問題,能AC......