9450번 - Heavy Chain Clusterization 스페셜 저지다국어

A group of biologists is trying to find a cure for a viral disease. They have tried many antibodies of various origins that could potentially fight the viral antigens, and have selected n antibodies that seem to work best during experiments.

Each antibody is identified by its heavy chain — a sequence of amino acids.

The set of antibodies form a similarity cluster, if at least one of the following holds:

• k-prefixes (first k amino acids) of all their heavy chains are equal;
• k-suffixes (last k amino acids) of all their heavy chains are equal.

In order to simplify the future research, biologists want to group antibodies to similarity clusters.

You need to split the given antibodies to a minimum number of similarity clusters.

The first line contains two integers n and k — the number of heavy chains and the length of sequence of amino acids to coincide (1 ≤ n ≤ 5 000, 1 ≤ k ≤ 550).

The following n lines contain sequences of amino acids that form heavy chains of antibodies. Each amino acid described with an uppercase English letter. Each heavy chain contains at least k and no more than 550 amino acids.

The first line of output must contain a single integer — the minimum number of similarity clusters. The following lines must contain descriptions of clusters, one per line.

Each description starts with mi — the number of antibodies in the cluster and is followed by mi integers — numbers of these antibodies. Antibodies are numbered in the order of appearance in the input starting from one.

Each antibody must be present in exactly one cluster.