Problem Statement

Implement agglomerative hierarchical clustering with single linkage and return cluster labels when exactly k clusters remain.

Algorithm:

1. Start with each point in its own cluster (n clusters).
2. Repeatedly merge the two clusters with the smallest single-linkage distance (minimum pairwise Euclidean distance between any two points across clusters).
3. Stop when the number of clusters equals k.
4. Assign labels: iterate through points in index order; the first point encountered in a cluster receives the next available label (0, 1, 2, ...).

Function signature:

def hierarchical_single(X: list, k: int) -> list:
    # returns list of integer cluster labels

Input Format

Line 1: n k — number of points and target number of clusters
Lines 2..n+1: space-separated floats — coordinates of each point

Output Format

One line: n space-separated integer cluster labels

Example

Input:

6 2
0.0 0.0
1.0 0.0
0.0 1.0
10.0 10.0
10.0 11.0
11.0 10.0

Output:

0 0 0 1 1 1

Notes

• The three near-origin points (0–2) form one cluster; the three near-(10,10) points (3–5) form another.
• Pairwise distances are computed once upfront using numpy.
• Label assignment follows first-occurrence order of point indices.