The Nostalgia for Infinity is an ancient ship that once carried hundreds of thousands, but now its crew is only a handful of Ultras –highly-modified humans adapted to the rigors of long interstellar spaceflight. And they are desperate to find a cure because most of their crew members are still infected with the Melding Plague, an alien virus that attacks human cells and machine nanotechnology in equal measure, perverting them into grotesque combinations. It is believed that some special mutations of the virus can help cure the dying Ultras. The Ultras’ patologists identified protein configurations as the essential constituents of the Melding Plague, some sort of genetic blueprint of the alien virus. Protein configurations are collections of proteins without any internal order and in which proteins can occur several times. For example, the following is the protein configuration last found in the infected blood of Nostalgia for Infinity’s captain John Brannigan: POMC CAD CAD SCN5A XIRP2 SCN5A ELTD1. Protein configurations mutate according to the individual mutation of its proteins. In 1-step muta- tion all proteins in the configuration that can mutate indeed mutate, and those which cannot mutate stay the same. Mutations continue over and over, changing configurations step by step. Fortunately, Ultras’ pathologists have identified protein configurations that are curable with appropriate therapies. Then, the hope for an Ultra infected with the Melding Plague is to have the protein configuration of the virus mutating to a curable protein configuration. Of course, therapies must be applied within a limit of mutation steps. A protein mutation is described by an ordered pair of protein names (p,q) stating that protein p mutates to protein q. If M = {(CAD, CELR2), (ELTD1, XIRP2)} is a collection of protein mutations, then the protein configuration of the virus in captain Brannigan’s blood, depicted above, mutates by M in 1-step to the protein configuration: POMC CELR2 CELR2 SCN5A XIRP2 SCN5A XIRP2. Please remember that because the order in the protein configurations is immaterial, the first con- figuration can be written in 1260 different ways, and the 1-step mutation just shown in 630 different ways. Your task today is to help the surviving Ultras by building a program that, given a collection of protein mutations M, an initial protein configuration I, a cure protein configuration C, and a natural number n representing a search bound: • if I mutates to C within at most n steps, computes the minimal number of such mutation steps; • otherwise, it must inform the Ultras that I cannot mutate to C within n steps. To easy your burden, Ultras’ pathologist are providing you with extra knowledge: they have iden- tified that if a cure by this method exists, one need to consider only deterministic mutations M, i.e., if (p,q1) and (p,q2) are in M, then q1 = q2. Input The input consists of several test cases. A test case begins with a line containing four natural numbers NM, NI, NC, and n separated by a blank, and with 0 ≤ NM,NI,NC,n ≤ 1000.
2/3 If NM , NI , and NC are greater than 0, then NM + NI + NC lines follow. The first NM lines define the collection M of protein mutations in which each line consists of a pair of strings p and q separated by a blank, representing protein mutation (p, q). Each one of the following NI lines consist of a string p and a natural number i separated by a blank, representing the number of occurrences i of protein p in the initial protein configuration I. Each one of the last NC lines consist of a string q and a natural number c separated by a blank, representing the number of occurrences c of protein q in the cure protein configuration C. The natural number n defines the search bound. TheinputendswithNM =NI =NC =n=0. Output For each test case your program must output exactly one line as follows: • if M is not deterministic, then output: Protein mutations are not deterministic • if M is deterministic and I mutates to C by M in at most n mutation steps with a minimum of k mutation steps, then output: Cure found in k mutation(s) • otherwise output: Nostalgia for Infinity is doomed Sample Input 2543 CAD CELR2 ELTD1 XIRP2 POMC 1 CAD 2 SCN5A 2 XIRP2 1 ELTD1 1 POMC 1 CELR2 2 SCN5A 2 XIRP2 2 2333 GP183 NALCN CAC1S GP183 CAC1S 2 YCFI 1 MRP6 3 YCFI 1 MRP6 3 NALCN 2 2331 GP183 NALCN CAC1S GP183 CAC1S 2 YCFI 1
3/3 MRP6 3 YCFI 1 MRP6 3 NALCN 2 3212 CAD YCFI ELTD1 XIRP2 CAD SCN5A CAD 1 YCFI 1 YCFI 2 0000 Sample Output Cure found in 1 mutation(s) Cure found in 2 mutation(s) Nostalgia for Infinity is doomed Protein mutations are not deterministic