樹狀數組經典的應用。把每個公路看作(a,b)一條邊，首先按a爲第一關鍵字，b爲第二關鍵字從大到小排序。然後維護一個序列A[i]，表示某時刻當前已經連到b的邊數，用樹狀數組維護其前綴和Sum[i]=A[1]+A[2]+...+A[i]。當插入一條邊(a,b)時，與這條邊相交的邊數就是Sum[b-1]，令Ans加上Sum[b-1]，然後修改A[b]加1。

由於邊已經排過序，與每次添加的邊相交的邊數恰好可以從前b-1個A中統計出。時間複雜度爲O((N+M)log(N+M))。

/* 
 * Problem: pku3067 japan
 * Author: Guo Jiabao
 * Time: 2009.3.19 13:38
 * State: Solved
 * Memo: 樹狀數組統計
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXM=1001;
using namespace std;
typedef __int64 big;
struct BIT
{
    big C[MAXM];
    int N;
    void init(int tN)
    {
        N=tN;
        memset(C,0,sizeof(C));
    }
    inline int lowbit(int x)
    {
        return x&(-x);
    }
    big sum(int p)
    {
        big rs=0;
        while (p)
        {
            rs+=C[p];
            p-=lowbit(p);
        }
        return rs;
    }
    void modify(int p,int delta)
    {
        while (p<N)
        {
            C[p]+=delta;
            p+=lowbit(p);
        }
    }
}B;
struct highway
{
    int x,y;
}H[MAXM*MAXM];
int N,M,K;
big Ans;
inline int cmp(const void *a,const void *b)
{
    if (((highway *)a)->x > ((highway *)b)->x) return -1;
    if (((highway *)a)->x < ((highway *)b)->x) return 1;
    if (((highway *)a)->y > ((highway *)b)->y) return -1;
    return 1;
}
void init()
{
    scanf("%d%d%d",&N,&M,&K);
    B.init(M);
    for (int i=1;i<=K;i++)
        scanf("%d%d",&H[i].x,&H[i].y);
    qsort(H+1,K,sizeof(H[0]),cmp);
    Ans=0;
}
void deal()
{
    for (int i=1;i<=K;i++)
    {
        Ans+=B.sum(H[i].y-1);
        B.modify(H[i].y,1);
    }
}
int main()
{
    int i,T;
    freopen("japan.in","r",stdin);
    freopen("japan.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        deal();
        printf("Test case %d: %I64dn",i,Ans);
    }
    return 0;
}