CF1450B.Balls of Steel

You have $n$ distinct points $(x_1, y_1),\ldots,(x_n,y_n)$ on the plane and a non-negative integer parameter $k$. Each point is a microscopic steel ball and $k$ is the attract power of a ball when it's charged. The attract power is the same for all balls.

In one operation, you can select a ball $i$ to charge it. Once charged, all balls with Manhattan distance at most $k$ from ball $i$ move to the position of ball $i$. Many balls may have the same coordinate after an operation.

More formally, for all balls $j$ such that $|x_i - x_j| + |y_i - y_j| \le k$, we assign $x_j:=x_i$ and $y_j:=y_i$.

An example of an operation. After charging the ball in the center, two other balls move to its position. On the right side, the red dot in the center is the common position of those balls.

Your task is to find the minimum number of operations to move all balls to the same position, or report that this is impossible.

平面上有 $n$ 个互不相同的点 $(x_1, y_1),\ldots,(x_n,y_n)$，以及一个非负整数参数 $k$。每个点代表一个微小的钢球，$k$ 表示当某个球被充电时的吸引力大小；所有球的吸引力大小均相同。

在一次操作中，你可以选择一个球 $i$ 对其充电。一旦被充电，所有与球 $i$ 的曼哈顿距离不超过 $k$ 的球都会移动到球 $i$ 的位置。一次操作后，多个球可能位于同一坐标处。

更准确地说，对所有满足 $|x_i - x_j| + |y_i - y_j| \le k$ 的球 $j$，我们令 $x_j:=x_i$ 且 $y_j:=y_i$。

一次操作的示例。中心球被充电后，另外两个球移动至其中心位置。右侧图中，中心的红点即为这些球共同的新位置。

你的任务是求出将所有球移动至同一位置所需的最少操作次数；若不可能实现，则报告该情况。

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains two integers $n$, $k$ ($2 \le n \le 100$, $0 \le k \le 10^6$) — the number of balls and the attract power of all balls, respectively.

The following $n$ lines describe the balls' coordinates. The $i$-th of these lines contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^5$) — the coordinates of the $i$-th ball.

It is guaranteed that all points are distinct.

第一行包含一个整数 $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$ 个小球的坐标。

保证所有点互不相同。

For each test case print a single integer — the minimum number of operations to move all balls to the same position, or $-1$ if it is impossible.

对于每个测试用例，输出一个整数——将所有球移动到同一位置所需的最少操作次数；如果无法实现，则输出 $-1$。

In the first test case, there are three balls at $(0, 0)$, $(3, 3)$, and $(1, 1)$ and the attract power is $2$. It is possible to move two balls together with one operation, but not all three balls together with any number of operations.

In the second test case, there are three balls at $(6, 7)$, $(8, 8)$, and $(6, 9)$ and the attract power is $3$. If we charge any ball, the other two will move to the same position, so we only require one operation.

In the third test case, there are four balls at $(0, 0)$, $(0, 1)$, $(0, 2)$, and $(0, 3)$, and the attract power is $1$. We can show that it is impossible to move all balls to the same position with a sequence of operations.

在第一个测试用例中，有三个球分别位于 $(0, 0)$、$(3, 3)$ 和 $(1, 1)$，吸引力为 $2$。可以通过一次操作将其中两个球移动到同一位置，但无论进行多少次操作，都无法使全部三个球到达同一位置。

在第二个测试用例中，有三个球分别位于 $(6, 7)$、$(8, 8)$ 和 $(6, 9)$，吸引力为 $3$。若对任意一个球施加电荷，则其余两个球均会移动至该球所在位置，因此仅需一次操作。

在第三个测试用例中，有四个球分别位于 $(0, 0)$、$(0, 1)$、$(0, 2)$ 和 $(0, 3)$，吸引力为 $1$。可以证明：无论采用何种操作序列，都不可能使所有球到达同一位置。