Dancing Group X25630

The dancing group Canchuba consists of n dancers, wearing dresses of different colors. Initially all n dancers stand in a single row. Canchuba’s choreographer, Paul Zynoulus, has designed m special movements. Each of these movements takes a minute to perform, and results in a change in the ordering of some dancers.

Now Paul is designing a new dance for the Measharan Dancing Contest. He wants the dancers to be arranged in a specific order before the dance, and in another specific order after the dance (however, if two dancers wear dresses of the same color, they can be arranged in an arbitrary way). He wants to know whether it is possible to combine the movements already designed by him to obtain this goal. There is one restriction: the whole dance must take at most 10 minutes.

Edit: The time limit should be 10, not 8.

Input

The first row contains two numbers n, m, 2≤ n≤ 80, 1≤ m≤ 15, where n is the number of dancers, and m is the number of movements.

The second row contains a single n-letter word. Its i-th letter denotes the color of the dancer who is initially standing at i-th place in the row.

The third row contains a single n-letter word. Its i-th letter denotes the color expected to stand at i-th place in the row after the dance.

Each of the following m rows contains a description of a movement. It consists of numbers c, a₁, a₂, …, a_c separated with single spaces, where c (1 ≤ c ≤ n) denotes the number of dancers which move. This describes a movement which moves dancer at a₁ to a₂, dancer at a₂ to a₃, …, dancer at a_c to a₁.

Output

If it is impossible to achieve the requested arrangement in 8 moves, output NO. Otherwise enter numbers of movements to perform, separated with single spaces. If there are several solutions, output one which requires the smallest number of movements. If there are several smallest solutions, output the lexicographically first one (if we have two solutions which perform the same movements 1 … t−1 but a different t-th movement, the one with a smaller number in movement i is lexicographically smaller).