题目描述

Those Who Know About Cows are aware of the way cows group into 'Cow Neighborhoods'. They have observed Farmer John's N (1 <= N <= 100,000) cows (conveniently numbered 1..N) as they graze, each at her own unique integer rectilinear coordinate, on a pasture whose X and Y coordinates are in the range 1..1,000,000,000.
Two cows are neighbors if at least one of two criteria is met:
1) If the cows are no further than some integer Manhattan distance C (1 <= C <= 1,000,000,000) apart, they are neighbors. [Manhattan distance is calculated as d = |x1-x2| + |y1-y2|.]
2) If cow A is a neighbor of cow Z and cow B is a neighbor of cow Z, then cow A is a neighbor of cow B (the 'transitive closure of neighbors').
Given the locations of the cows and the distance C, determine the the number of neighborhoods and the number of cows in the largest neighborhood.
By way of example, consider the pasture below. When C = 4, this pasture has four neighborhoods: a big one on the left, two neighborhoods of size 1 (the lonesome cows), and a huge neighborhood on the right with 60 different cows.
.....................................*................. 
....*...*..*.......................***................. 
......*...........................****................. 
..*....*..*.......................*...*.******.*.*..... 
........................*.............***...***...*.... 
*..*..*...*..........................*..*...*..*...*... 
.....................................*..*...*..*....... 
.....................................*..*...*..*....... 
...*................*.................................. 
.*..*............................*.*.*.*.*.*.*.*.*.*.*. 
.*.....*..........................*.*.*.*.*.*.*.*.*.*.* 
....*.................................................. 
The input file describes cow locations by integer X,Y coordinates, where the lower left corner is (1,1) and cows close to that corner appear at both (2,2) and (5,1) in the example above.
For a given pasture, determine both the number of cow neighborhoods and the number of cows resident in the largest cow neighborhood.
The above picture is sample test case 2, which will be evaluated for you upon submission.
Partial feedback for some test cases will be provided on the first 10 submissions.
Time Limit: 2 seconds
Memory Limit: 32MB
了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：
1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi – xil+IYi – Yil≤C.
2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．
给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

输入格式：

Line 1: Two space-separated integers: N and C
Lines 2..N+1: Line i+1 describes cow i's location with two
space-separated integers: X_i and Y_i

输出格式：

Line 1: A single line with a two space-separated integers: the number of cow neighborhoods and the size of the largest cow neighborhood.

输入样例#1：

4 2 
1 1 
3 3 
2 2 
10 10 

输出样例#1：

2 3