General Bytor

Time limit1sMemory limit128 MB

Summary

Given two permutations of n unit types and m cyclic position-shift orders, find the shortest (then lexicographically smallest) sequence of at most 10 orders that transforms the start into the target.

Level: Hard8 of 10
Topics: Brute force, String, Hash map, BFS
Solved: No attempts yet

Problem

The Qbits are coming!

General Bytor, commander-in-chief of Fort Bytemore, suddenly woke up, rushed to headquarters, and checked the battle plan. The situation did not look good. Every important strategic position of the fort held exactly one army unit, but some units were in the wrong place. Worse still, giving orders had become very difficult: the Qbits' secret agents had used quantum teleportation to kidnap every cryptographer in the fort. Now Bytor can issue only the few orders he memorized during recent training.

Each order corresponds to a single line running through a sequence of strategic positions. When an order is given, every army unit on that line advances one step to the next position along the line. Each line is in fact a cycle, so after the movement every strategic position again holds exactly one unit.

About half an hour remains before the battle begins, and in that time Bytor can perform at most 10 orders. Given the initial and requested arrangements, write a program that decides whether a short enough sequence of orders leads from the initial arrangement to the requested one, and if so, finds it.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n \le 75$ , $1 \le m \le 10$ ), separated by a single space. $n$ is the number of strategic positions and $m$ is the number of lines.

The second line contains a word of $n$ lowercase English letters. The $i$ -th letter is the type of the unit currently located at the $i$ -th strategic position (given by the old Bytean military code). Several units may share the same type.

The third line also contains a word of $n$ lowercase letters. It gives the unit types that must occupy strategic positions $1, 2, \dots, n$ after the movements. This word is different from the one on the second line.

Each of the next $m$ lines describes one line in the form $c\; a_1\; a_2\; \dots\; a_c$ (numbers separated by single spaces). The first number $c$ is the number of strategic positions on the line, and $a_i$ ( $1 \le a_i \le n$ ) is the $i$ -th position on the line. All numbers on a single line are distinct. Issuing this order moves the units as follows: $a_1 \to a_2,\; a_2 \to a_3,\; \dots,\; a_{c-1} \to a_c,\; a_c \to a_1$ .

Output

If the requested arrangement cannot be reached with at most 10 orders, output the single word NIE (Polish for "no").

Otherwise output at most 10 line numbers (each between $1$ and $m$ ), separated by spaces, that Bytor should issue in order. If several sequences work, output the one with the fewest orders; if there are still several, output the lexicographically smallest one. (Let $t$ be the first position at which two equal-length sequences differ; the sequence whose $t$ -th order has the smaller line number is the lexicographically smaller one.)

Examples3

Example 1

Input

12 6
abcdefghijkl
cdabghieflkj
2 10 11
4 4 3 2 1
5 9 8 7 6 5
4 1 2 3 4
5 5 6 7 8 9
2 11 12

Expected output

1 2 2 3 3 6 1

Example 2
Input
```
3 1
abc
cab
3 1 2 3
```
Expected output
```
1
```
Example 3
Input
```
4 2
abcd
badc
2 1 2
2 3 4
```
Expected output
```
1 2
```