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......