思路：把所有涉及到的点按（x+y）的奇偶分成两部分点，对所有的1*2的骨牌，都有(x+y)为偶数的建到奇数的边。求一次最大匹配，就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define Maxn 2010
using namespace std;
int match[Maxn],map[Maxn][Maxn],vi[Maxn],ny,nx,graphic[Maxn][Maxn];
struct Point{
int x, y;
}hori[Maxn],vert[Maxn];
void init()
{
memset(map,,sizeof(map));
memset(graphic,,sizeof(graphic));
nx=ny=;
}
int dfs(int u)
{
int i,j;
for(i=;i<=ny;i++)
{
if(!vi[i]&&graphic[u][i])
{
vi[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
}
return ;
}
int main()
{
int n,m,i,j,x,y;
while(scanf("%d%d",&n,&m),n||m)
{
init();
int mx,my;
mx=my=;
for(i=;i<=n;i++)
{
scanf("%d%d",&hori[i].x,&hori[i].y);
map[hori[i].x][hori[i].y]=;
map[hori[i].x+][hori[i].y]=;
mx=max(mx,hori[i].x+);
my=max(my,hori[i].y);
}
for(i=;i<=m;i++)
{
scanf("%d%d",&vert[i].x,&vert[i].y);
map[vert[i].x][vert[i].y]=;
map[vert[i].x][vert[i].y+]=;
mx=max(mx,vert[i].x);
my=max(my,vert[i].y+);
}
nx=ny=;
for(i=;i<=mx;i++)
for(j=;j<=my;j++)
{
if(map[i][j])
{
if((i+j)%==)
map[i][j]=++nx;
else
map[i][j]=++ny;
}
}
for(i=;i<=n;i++)
{
x=map[hori[i].x][hori[i].y];
y=map[hori[i].x+][hori[i].y];
if((hori[i].x+hori[i].y)%==)
graphic[x][y]=;
else
graphic[y][x]=;
}
for(i=;i<=m;i++)
{
x=map[vert[i].x][vert[i].y];
y=map[vert[i].x][vert[i].y+];
if((vert[i].x+vert[i].y)%==)
graphic[x][y]=;
else
graphic[y][x]=;
}
memset(match,-,sizeof(match));
int ans=;
for(i=;i<=nx;i++)
{
memset(vi,,sizeof(vi));
if(dfs(i))
ans++;
}
printf("%d\n",ans);
}
return ;
}