2006. [USACO Open08]牛的邻居

【题目描述】

那些拥有丰富的牧奶牛经验，见得多了的人很熟悉奶牛们按照相邻关系分组的一套方式。他们注意到Farmer John的$N（1<=N<=100,000）$头奶牛（按顺序编号为$1..N$）正在牧场上吃草，每头奶牛都位于她独一无二的直角坐标处，这是一片$X$和$Y$坐标均处于$1..10^9$范围内的草地。

两头奶牛是相邻的，如果以下两个条件之一满足：

1）如果这两头牛的曼哈顿距离不超过C，她们就是相邻的。（曼哈顿距离计算公式为$d=|x_1-x_2|+|y_1-y_2|$）

2）如果奶牛A和奶牛Z相邻，而且奶牛B也和奶牛Z相邻，那么奶牛A就和奶牛B相邻（相邻关系具有传递性）。

给出所有奶牛的位置和C的值，计算奶牛分成的组数，以及最大的一组奶牛数目。

举个例子，考虑如下的牧场。当C=4时，有4组奶牛：左边的一组，两个仅含1头牛的组（孤独的奶牛），以及右边巨大的一组，它包含60头牛。

.....................................*.................

....*...*..*.......................***.................

......*...........................****.................

..*....*..*.......................*...*.******.*.*.....

........................*.............***...***...*....

*..*..*...*..........................*..*...*..*...*...

.....................................*..*...*..*.......

.....................................*..*...*..*.......

...*................*..................................

.*..*............................*.*.*.*.*.*.*.*.*.*.*.

.*.....*..........................*.*.*.*.*.*.*.*.*.*.*

....*..................................................

输入文件给出了所有牛的坐标，其中左下角是$(1,1)$，而上述例子中，接近左下角的两头奶牛是$(2,2)$和$(5,1)$。

对于一片给定的牧场，计算奶牛分成的组数，以及最大一组的奶牛数。

【输入格式】

第1行：两个空格隔开的整数N和C。

第2..N+1行：第i+1行给出了i号奶牛的坐标$X_i$和$Y_i$。

【输出格式】

一行两个整数，由空格隔开：奶牛分成的组数，和最大一组奶牛的数量。

【样例输入】

4 2

1 1

3 3

2 2

10 10

【样例输出】

2 3

【提示】

有两组，一个是前三头牛，另一个是最后一头牛。因而最大的一组有3头牛。

【来源】

Richar Ho,2006