Problem Statement

Compute the mean silhouette score for a clustering assignment.

For each point i:

• a(i) = mean Euclidean distance to all other points in the same cluster
• b(i) = minimum mean Euclidean distance to points in any other cluster (over all other clusters)
• s(i) = (b(i) - a(i)) / max(a(i), b(i))
• If point i is the only member of its cluster, s(i) = 0.

The overall score is the mean of all individual silhouette scores.

Function signature:

def silhouette_score(X: list, labels: list) -> float:

Input Format

Line 1: n d — number of points and number of dimensions
Lines 2..n+1: d feature values followed by cluster label (all space-separated)

Output Format

One line: the mean silhouette score (10 significant figures)

Example

Input:

6 2
0.0 0.0 0
1.0 0.0 0
0.0 1.0 0
10.0 10.0 1
10.0 11.0 1
11.0 10.0 1

Output:

0.9196222281

Notes

• A score close to 1 means clusters are well-separated and compact.
• A score near 0 means clusters overlap; negative values indicate misclassified points.
• Compute all pairwise Euclidean distances first for efficiency.