Recently encountered this problem in a competition. Tried solving it using graphs, creating neighbors and then finding the number of nodes in different disconnected sub-graphs. But the creation of neighbors itself is O(n^2) and hence was getting TLE. I have been trying to figure out a way to solve this without creating neighbors or find a more efficient way to create neighbors, but haven't been able to do so. I also thought of using union-find, but again computing distances between each pair is O(n^2). Any help would be really appreciated.

#### Problem:

There are *n* circles, for each of which center ( *x* , *y* ) and radius *r* are provided. These circles can intersect each other. Circles are said to be intersecting if they touch each other or cross each other's circumference. A cluster of circles is defined as a group of circles which are in contact with each other. So, if *C1* intersects *C2* and *C2* intersects *C3*, then *C1*, *C2*, *C3* are in a cluster even if *C1* and *C3* don't directly intersect each other. We have to find the cluster with the largest number of circles. Print the number of circles in the largest cluster and the smallest circle index in that cluster. If 2 clusters have the same number of circles, print the one with the smallest circle index.

#### Constraints:

*0<= n <= 1e5*, *0 <= r <= 50*, *0 <= x, y <= 1e4*

#### Time limit:

*3s* for *50* test cases.

#### Additional info:

For 20% test cases, *0 <= n <= 100*

For 30% test cases, *100 <= n <= 1000*

For 30% test cases, *1000 <= n <= 1e4*

For 20% test cases, *1e4 <= n <= 1e5*