← 返回题目列表

Codeforces · 1450/B

B. 钢球

中文机器翻译题面 查看原题

平面上有 $$$n$$$ 个不同点 $$$(x_1, y_1),\ldots,(x_n,y_n)$$$ 和一个非负整数参数 $$$k$$$。每个点都是一个微小的钢球,$$$k$$$ 是钢球充电时的吸引力。所有球的吸引力都相同。

在一次操作中,您可以选择一个球 $$$i$$$ 为其充电。一旦充电,所有与球 $$$i$$$ 曼哈顿距离最多 $$$k$$$ 的球都会移动到球 $$$i$$$ 的位置。一次操作后,许多球可能具有相同的坐标。

更正式地说,对于所有球 $$$j$$$ 使得 $$$|x_i - x_j| + |y_i - y_j| \le k$$$,我们分配 $$$x_j:=x_i$$$ 和 $$$y_j:=y_i$$$。

操作示例。在中心的球充电后,另外两个球移动到其位置。右边,中间的红点就是这些球的共同位置。

你的任务是找到将所有球移动到同一位置的最少操作次数,或者报告这是不可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$0 \le k \le 10^6$$$) - 分别是球的数量和所有球的吸引力。

以下 $$$n$$$ 行描述了球的坐标。这些行中的第 $$$i$$$ 包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$0 \le x_i, y_i \le 10^5$$$) — 第 $$$i$$$ 球的坐标。

保证所有点都是不同的。

输出

对于每个测试用例,打印一个整数 - 将所有球移动到同一位置的最小操作数,如果不可能,则打印 $$$-1$$$。

示例

输入 #1

3
3 2
0 0
3 3
1 1
3 3
6 7
8 8
6 9
4 1
0 0
0 1
0 2
0 3

输出 #1

-1
1
-1

注意

在第一个测试用例中,有三个球,分别位于 $$$(0, 0)$$$、$$$(3, 3)$$$ 和 $$$(1, 1)$$$,吸引力为 $$$2$$$。可以通过一次操作来移动两个球,但不能通过任意次数的操作来移动所有三个球。

在第二个测试用例中,有三个球,分别位于 $$$(6, 7)$$$、$$$(8, 8)$$$ 和 $$$(6, 9)$$$,吸引力为 $$$3$$$。如果我们对任何一个球进行冲锋,另外两个球就会移动到相同的位置,因此我们只需要一次操作。

在第三个测试用例中,有四个球分别位于$$$(0, 0)$$$、$$$(0, 1)$$$、$$$(0, 2)$$$和$$$(0, 3)$$$,吸引力为$$$1$$$。我们可以证明,不可能通过一系列操作将所有球移动到同一位置。