Məsələlər
Heavy Chain Clusterization
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 \textbf{n} antibodies that seem to work best during experiments.
Each antibody is identified by its \textit{heavy chain} --- a sequence of amino acids.
The set of antibodies form a \textit{similarity cluster}, if at least one of the following holds:
\begin{itemize}
\item \textbf{k}-prefixes (first \textbf{k} amino acids) of all their heavy chains are equal;
\item \textbf{k}-suffixes (last \textbf{k} amino acids) of all their heavy chains are equal.
\end{itemize}
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.
\InputFile
The first line contains two integers \textbf{n} and \textbf{k} --- the number of heavy chains and the length of sequence of amino acids to coincide (\textbf{1} ≤ \textbf{n} ≤ \textbf{5000}, \textbf{1} ≤ \textbf{k} ≤ \textbf{550}).
The following \textbf{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 \textbf{550} amino acids.
\OutputFile
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 \textbf{m_i} --- the number of antibodies in the cluster and is followed by \textbf{m_i} 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.
Giriş verilənləri #1
4 1 AA AB BB BA
Çıxış verilənləri #1
2 2 1 2 2 3 4
Giriş verilənləri #2
3 2 ABA BAB XY
Çıxış verilənləri #2
3 1 1 1 2 1 3