了解奶牛们的人都知道,奶牛喜欢成群结队。观察约翰的 只奶牛,你会发现她们已经结成了几个 “群” 。每只奶牛在吃草的时候有一个独一无二的位置坐标 , 。当满足 下列两个条件之一,两只奶牛 和 是属于同一个群的:
1.两只奶牛的曼哈顿距离不超过 ,即
2.两只奶牛有共同的邻居。即,存在一只奶牛 ,使 与 , 与 均同属一个群。
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛。
第 行输入两个整数 和 ,之后 行每行输入两个整数 表示一只奶牛的坐标。
仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开。
4 2 1 1 3 3 2 2 10 10
2 3
对于 的数据,,,,。
Gold