Cubes (solution using graphs)

The task

Parents gave Pete a set of children's cubes. Since Petya will soon go to school, they bought him cubes with letters. A letter is written on each of the six faces of each cube.

Now Petya wants to brag to an older sister that he has learned to read. For this, he wants to add her name from cubes. But it turned out to be quite difficult to do - because different letters can be on the same cube, and then Peter will not be able to use both letters in a word. True, the same letter can occur on different cubes. Help Pete!

Given a set of cubes and the name of the sister. Find out if you can lay out her name with the help of these cubes, and if so, in what order you should put the cubes.

Input

The first line of the input file contains the number N (1 <= N <= 100) - the number of cubes in Petit's set. The second line contains the name of Petina's sister - a word consisting only of capital Latin letters, no longer than 100 characters. The next N lines contain 6 letters each (only large Latin letters), which are written on the corresponding cube.

Conclusion

In the first line of the output file output YES, if you put the name of Petina's sister with the given cubes, and N0 - otherwise.

If the answer is YES, then in the second line output M different numbers from the range l..N, where M is the number of letters in the name of Petina's sister, ie, the number should be the number of the cube that should be placed on the ie place when composing the name of Petina's sister. The cubes are numbered from 1, in the order in which they are specified in the input file. If there are several solutions, output any. Separate numbers with spaces.

  Input Example Output Example
 4 n0 
 ANN 
 ANNNNN 
 BCDEFG 
 HIJKLM 
 NOPQRS 

 5 YES 
 HELEN 2 1 3 5 4 
 ABCDEF 
 GHIJKL 
 MNOPQL 
 STUVWN 
 EIUOZK 

Solution [up]

For this problem, we compose a graph as follows: as base vertices, we will consider given cubes, as well as vertices corresponding to letters that can be written on given cubes (26 uppercase letters of the Latin alphabet). We also add a vertex-source (we connect it with all the vertices corresponding to the cubes) and a vertex-flow (we connect with it all the vertices corresponding to the letters).

Since only one letter can be used per die, the weights of the arcs from the source to the cubes are 1.

A fragment of the graph from the vertices corresponding to the capital letters of the Latin alphabet, to the drain is determined by the name of Petina's sister, which, according to the conditions of the problem, is required to be made up of the initial cubes. Since the name of Petina's sister can include repeated letters, incrementing is used when forming the weight of the corresponding arc.

Finally, for each letter on each cube, an arc is constructed from the corresponding cube to the corresponding letter.

To get an answer to the question posed in the problem (“Find out whether it is possible to lay out its name with the help of these cubes and, if so, in what order you should put the cubes”), after constructing the maximum flow using the Ford-Fulkerson method, you should calculate on a given graph max outgoing flow Mach. If the value of Mach is not equal to the length of the Name name, then the answer is negative (N0), otherwise - positive (YES). In order to output the numbers of the used cubes in the order ensuring the construction of the name, it is necessary for each letter of the name to find such a vertex k in the column (and output its number) that the flow from the vertex to the letter is 1.

Formal description [up]

  Cubes ()
 1. Read the task input data from the file.
 2. Create a bichromatic graph in which the vertices are cubes and letters of English
    the alphabet.  Link cubes with letters that are present on the cube.
 2. Create a vertex-source and connect it with the vertices of the graph, which
    meet the cubes.  The throughput for these edges is one.
 3. Create a vertex-drain and connect it with vertex-letters, which 
    present in the sister's name.  Bandwidth - quantity
    repetitions of the letter in the name.
 4. Find the maximum flow algorithm Ford-Fulkerson 
    between the source and drain.
 5. If the number of cubes is less than the length of the name or if the stream from
    the source is not equal to the length of the name, then it is assumed that it is impossible to add the name, 
    otherwise find a sequence of cubes.