#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<1|1

#define All 1,N,1

#define N 500010

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

struct city{

  int p,r;

}t[N];

bool cmp(city x,city y){

    return x.p<y.p;

}

int maxv[N*],n,dp[N];

void pushup(int rt){

    maxv[rt]=max(maxv[rt<<],maxv[rt<<|]);

}

void build(int l,int r,int rt){

    maxv[rt]=;

    if(l==r){

        return;

    }

    int m=(l+r)>>;

    build(lson);

    build(rson);

}

void update(int p,int v,int l,int r,int rt){

      if(l==r){

        maxv[rt]=max(maxv[rt],v);

        return;

      }

      int m=(l+r)>>;

      if(p<=m)update(p,v,lson);

      else update(p,v,rson);

      pushup(rt);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r)

        return maxv[rt];

    int m=(l+r)>>;

    int ans=;

    if(L<=m)ans=max(ans,query(L,R,lson));

    if(R>m)ans=max(ans,query(L,R,rson));

    return ans;

}

int main()

{

    int ca=;

    while(~scanf("%d",&n)){

        memset(dp,,sizeof(dp));

        for(int i=;i<n;++i)

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

        sort(t,t+n,cmp);

        build(,n,);

        int maxn=;

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

            dp[i]=query(,t[i].r,,n,)+;

            maxn=max(maxn,dp[i]);

            update(t[i].r,dp[i],,n,);

        }

        printf("Case %d:\n",++ca);

        if(maxn>)

               printf("My king, at most %d roads can be built.\n",maxn);

        else

             printf("My king, at most %d road can be built.\n",maxn);

        printf("\n");

    }

return ;

}