Problem description

Back
Show PDF
Magnetyczne Krasnale
(J)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

We Wrocławiu testowane są nowe magnetyczne krasnale. Magnetyczne krasnale, oprócz bycia (uroczą) wizytówką miasta, mogą zostać naładowane. Naładowany krasnal natychmiast przyciąga do siebie wszystkie krasnale w pobliżu. Taka funkcjonalność ma wiele zalet, między innymi, być może, da się w ten sposób zebrać wszystkie krasnale w jednym miejscu jedynie poprzez naładowania. Twoim zadaniem jest rozstrzygnąć, czy dla zadanego ustawienia krasnali jest to możliwe, a jeśli tak – jaka minimalna liczba naładowań jest do tego potrzebna.

Dane jest rozstawienie N krasnali. Każdy krasnal znajduje się w pewnym punkcie płaszczyzny, i-ty w punkcie o współrzędnych (Xi,Yi). W pobliżu danego krasnala są wszystkie krasnale znajdujące się w odległości taksówkowej nie większej niż D od tego krasnala, tj. krasnal j-ty jest w pobliżu krasnala i-tego, jeśli |Xi−Xj| + |Yi−Yj| ≤ D. Naładowanie krasnala skutkuje tym, że wszystkie krasnale w jego pobliżu natychmiast przesuwają się do punktu (Xi,Yi), gdzie i to numer naładowanego krasnala. W jednym punkcie może znajdować się wiele krasnali. Naładowań należy dokonywać po kolei, nie można naładowywać wielu krasnali jednocześnie. Powiemy, że krasnale można zebrać, jeśli istnieje ciąg naładowań, po którym wszystkie krasnale znajdą się w jednym punkcie.

Przykład operacji naładowania. Po naładowaniu krasnala w środku dwa inne krasnale przesuwają się na jego pozycję. Po prawej czerwona kropka jest wspólną pozycją tych krasnali.

Wejście

W pierwszym wierszu wejścia znajduje się liczba przypadków testowych T.

W pierwszym wierszu każdego przypadku testowego znajduje się liczba naturalna N oraz parametr D.

W każdym z kolejnych N wierszy znajduje się para liczb naturalnych Xi, Yi, oznaczających współrzędne i-tego krasnala. Pary współrzędnych nie powtarzają się, tzn. nie ma dwóch krasnali początkowo stojących w tym samym miejscu.

Wyjście

Dla każdego przypadku testowego należy wypisać w jednym wierszu pojedynczą liczbę – minimalną liczbę naładowań, jakie są potrzebne do zebrania krasnali, albo -1, jeśli nie da się zebrać krasnali.

Ograniczenia

1 ≤ T ≤ 100, 2 ≤ N ≤ 100, 0 ≤ D ≤ 106, 0 ≤ Xi, Yi ≤ 100 000.

Przykłady

Wejście Wyjście Wyjaśnienie 
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

  • W pierwszym przypadku testowym znajdują się trzy krasnale w punktach (0,0), (3,3) i (1,1), a D wynosi 2. Możliwe jest przesunięcie dwóch krasnali do tego samego punktu za pomocą jednego naładowania, ale nie da się zebrać wszystkich trzech krasnali przy użyciu dowolnej liczby naładowań.

  • W drugim przypadku testowym znajdują się trzy krasnale w punktach (6,7), (8,8) i (6,9), a D wynosi 3. Jeśli naładujemy dowolnego krasnala, pozostałe dwa przesuną się na tę samą pozycję, więc potrzebujemy tylko jednej operacji naładowania.

  • W trzecim przypadku testowym znajdują się cztery krasnale w punktach (0,0), (0,1), (0,2) i (0,3), a D wynosi 1. Można wykazać, że przesunięcie wszystkich krasnali na tę samą pozycję za pomocą sekwencji naładowań jest niemożliwe.
Wejście Wyjście 
1
2 1000000
0 0 
100000 100000

1
Wejście Wyjście 
1
4 0
6 6
6 7
7 6
7 7

-1