#1604. [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

题目描述

了解奶牛们的人都知道,奶牛喜欢成群结队。观察约翰的 nn 只奶牛,你会发现她们已经结成了几个 “群” 。每只奶牛在吃草的时候有一个独一无二的位置坐标 xix_iyiy_i 。当满足 下列两个条件之一,两只奶牛 iijj 是属于同一个群的:

1.两只奶牛的曼哈顿距离不超过 cc,即 $\left| x_i - x_j \right| + \left| y_i - y_j \right| \leq c$

2.两只奶牛有共同的邻居。即,存在一只奶牛 kk,使 iikkjjkk 均同属一个群。

给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛。

输入格式

11 行输入两个整数 nncc,之后 nn 行每行输入两个整数 xi,yix_i,y_i 表示一只奶牛的坐标。

输出格式

仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开。

样例

4 2
1 1
3 3
2 2
10 10
2 3

数据规模与约定

对于 100%100\% 的数据,1n1051\leq n\leq 10^51xiyic1091\leq x_i,y_i,c \leq 10^9

题目来源

Gold