URI Online Judge | 1814

DNA Storage?

By Maratona de Programação 2003, IME-USP BR Brazil

Timelimit: 1

Charles University in Prague, by example of several other leading universities around the world, recently established an interdepartmental graduate program in computational biology. Ms. Dolejškova, member of the faculty, is currently interested in the problem of phylogenetic trees, and working with n chains of DNA. To simplify the work, Ms. Dolejškova decided to work only with gene chains of length m (i.e., all the chains have exactly m nitrogenous bases).

An interesting sub-problem involves storing the n chains in a disk. Yet, Ms. Dolejškova is using a naive scheme that requires n × m characters, besides the delimiters. I.e., all sequences are written in a text file, sequentially. Mr. Chuchle, a department mate and storage techniques expert, suggested an alternative that may be more economical.

According to Mr. Chuchle, you can store a chain and the information that allow it to transform into other. More specifically, consider two chains of DNA D1 = ACTA and D2 = AGTC, where A, C, G, T are the nitrogenous bases adenine, cytosine, guanine and thymine, respectively. Note that it is possible to turn D1 into D2 by exchanging the nitrogenous bases C and A of the 2 and 4 positions from D1 to G and C, respectively. Consider now a third chain D3 = CGTC. Only a modification is required to turn D2 into D3 and three changes are required to transform D1 into D3. Thus, is profitable to have the transitivity of the changes between the chains.

Ms. Dolejškova quickly observed that alternative storage scheme does not offer gains if the chains involved are very different. Thus, instead of using it promptly, she asked you to build a program that receives n chains, and determines the minimum number of changes that must be written (plus a chain) to make it possible in future to obtain again the original n chains. Based on the results provided by your program, Ms. Dolejškova will decide which system should be used in each instance of data.


Your program must work with multiple instances. The first line contains two integers, n and m, (0 ≤ n ≤ 100 and 1 ≤ m ≤ 1000) indicating the number of DNA chains and your length. Is given n strings in the next n lines, one per row, without additional spaces. Each string is a sequence of characters chosen from the alphabetic Σ = {A, C, G, T}. The value for n = 0 indicate the end of instances and must not be processed.


For each instance solved, you must print an identifier “Instancia” h (Instance in Portuguese) which h is an integer, sequential, growing and begin in 1. In the next line, you must print the minimum number of transformation which needs to be written for that instance. A blank line must be printed after each instance.

Sample Input Sample Output

3 4

4 5

0 0

Instancia 1

Instancia 2