Problem Statement

Implement the DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm.

Parameters:

• eps: the neighborhood radius (Euclidean distance)
• min_s: minimum number of points to form a dense region (core point threshold)

Algorithm:

1. Process points in index order (0, 1, 2, ...).
2. For each unvisited point i, find all points within Euclidean distance eps (its neighborhood, including itself).
3. If |neighborhood| < min_s, mark i as noise (-1) and continue.
4. Otherwise, start a new cluster, assign i to it, then BFS-expand: for each neighbor j, if j's neighborhood also has ≥ min_s points, add its unqueued neighbors to the queue. Assign all reachable points to this cluster (noise points can be reassigned).
5. Cluster IDs are assigned 0, 1, 2, ... in discovery order.

Function signature:

def dbscan(X: list, eps: float, min_s: int) -> list:
    # returns list of integer labels; -1 = noise

Input Format

Line 1: n eps min_s — number of points, epsilon radius, min samples
Lines 2..n+1: space-separated floats — coordinates of each point

Output Format

One line: n space-separated integer labels (-1 for noise, 0, 1, 2, ... for clusters)

Example

Input:

7 1.1 4
0.0 0.0
0.75 0.0
0.0 0.75
0.75 0.75
5.0 5.0
5.75 5.0
5.0 5.75

Output:

0 0 0 0 -1 -1 -1

Notes

• Points 0–3 are mutually within eps=1.1 and form a dense cluster (cluster 0).
• Points 4–6 each have only 3 neighbors within eps (< min_s=4), so they are noise.
• A noise point can later be absorbed into a cluster if it falls within the neighborhood of a core point.