|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||6||4||4||66.667%|
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:
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.
4 1 AA AB BB BA
2 2 1 2 2 3 4
3 2 ABA BAB XY
3 1 1 1 2 1 3