D. 无线中继

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

B 国下辖一片极地地区。该地气候、环境恶劣,极端天气频发,冻土广布,人烟稀少,长期以来不通网络,给来到该地考察和旅游的人员带来很大困扰。

某年月日,B 国政府聘请了联邦政府技术团队,专门研究在该地区接通网络的解决方案。经过研究,发现该地铺设有线线路成本过高,且以移动网络需求为主,因此技术团队决定采用无线中继的方法来使网络信号覆盖整片地区。具体来说,就是建设一些无线基站,其间没有有线线路连接,单纯依靠基站之间的无线中继将所有基站联通在一起。

为了更好地表述规划方案,技术团队将这片地区视为一个二维平面,并将方案中规划的 个基站视为平面上的点,其中第 个基站在平面上的坐标是 。

定义 表示 之间的曼哈顿距离。当两个基站 满足 时,它们将可以直接进行无线连接,否则不能。如果两个基站 无法直接相互连接,如果可以选择一系列中继基站 ,满足对于任意正整数 ,,且 ,则它们可以通过无线中继进行连接。我们把两两可以直接或间接连接上,且组内任何基站不能和组外任何基站直接或间接连接上的一组基站称作一个联通块。显然,一个理想的规划方案应该只有一个 个基站的联通块。然而事实上,规划方案可能出现错误,导致出现多个联通块。

现在,作为技术团队测试组骨干成员,你需要编写一个程序来对给定规划方案进行评估。如上所述,你会得到 个基站的坐标和基站连接距离极限 。你需要编写程序来计算出这些基站通过无线中继可能达到的联通情况,并报告联通块的数量和最大联通块的大小(即其所含基站数量)。

输入格式

第一行两个整数 ,含义如题。

接下来 行,第 行两个整数 ,含义如题。

输出格式

共两行,第 行表示联通块数量,第 行表示最大联通块大小。

样例

样例输入

4 2 
1 1 
3 3 
2 2 
10 10 

样例输出

2
3

数据范围与提示

对于的数据,。

对于的数据,。