logo AlgoBeat OnlineJudge
登录 注册

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

内存限制:64 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

1.两只奶牛的曼哈顿距离不超过 ,即

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

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

输入格式

行输入两个整数 ,之后 行每行输入两个整数 表示一只奶牛的坐标。

输出格式

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

样例

样例

样例输入 #1

4 2
1 1
3 3
2 2
10 10

样例输出 #1

2 3

数据范围与提示

对于 的数据,

Gold