← 返回 uber 的题目列表Minimum Triggers to Absorb All Balls
类型：online_judge
You are given n balls on a 2D plane, ball i at coordinate (x[i], y[i]).
When you "trigger" a ball, it starts absorbing other balls with chain propagation:
If two balls are on the same row (same y) and |x1 - x2| <= d, they can absorb each other.
If two balls are on the same column (same x) and |y1 - y2| <= d, they can absorb each other.
Once a ball is absorbed, it continues absorbing others under the same rules (transitively).
Each trigger ultimately absorbs exactly one connected component in the graph defined by these adjacency rules.
Compute the minimum number of triggers required to absorb all balls.
Input
First line: two integers n and d
Next n lines: two integers x[i] y[i]
Output
One integer: the minimum number of triggers.
Constraints
1 <= n <= 2e5
0 <= d <= 1e9
Coordinates fit in 32-bit signed integer.
Example
Input
5 2
0 0
2 0
5 0
2 3
2 5
Output
2
Example
Input
5 2
0 0
2 0
5 0
2 3
2 5
Output
2