Régiók
Egy megyén belül a településeket régiókba szeretnék csoportosítani. Ismerjük az egyes települések koordinátáit. Két település távolságán a koordináta-különbségeik abszolút értékének összegét értjük, azaz
$d((x,y),(a,b))=|x-a|+|y-b|$.
Két települést azonos régióba teszünk, ha egyikből a másikba el lehet jutni a régió településein keresztül úgy, hogy az egymást követő települések távolsága legfeljebb T kilométer.
Feladat
Írj programot, amely megadja, hogy a települések hány régiót alkotnak, és mely települések tartoznak egy régióba!
Bemenet
A REGIO.BE szöveges állomány első sorában a
városok N száma $(2\le N\le 100)$ és a régióba kerülés határát jelentő T távolság $(1\le T\le 2000)$ van.
A következő N sor mindegyikében egy-egy számpár van, az adott város
x- és y-koordinátája (0 és 1000 közötti egész számok), egy szóközzel elválasztva.
Kimenet
A REGIO.KI szöveges állomány első sorába a legkisebb K számot kell írni, ahány régióba lehet besorolni a településeket. A következő K sorba az egyes régiókat kell írni, tetszőleges sorrendben. Egy sorba a régióba tartozó települések sorszámát kell írni, egy-egy szóközzel elválasztva, növekvő sorrendben.
Példa
| regio.be | regio.ki |
| 6 50
100 100
100 220
100 120
300 100
120 240
310 90 |
3
1 3 5
2
4 6 |
Tesztadatok
