8521번 - General Bytor 다국어

Qbits are coming!

General Bytor, the commander-in-chief of Fort Bytemore, suddenly woke up, quickly went to the headquarters and checked the operational plan. Unfortunately, the situation didn't look well. At every important strategic position of the fort there was one army unit; however, some units were located at incorrect positions. Even worse, it turned out that there would be essential difficulties with giving orders. The reason for that was that Qbits' secret agents used quantum teleportation techniques to kidnap all cryptographers from the fort! Without them, Bytor wouldn't be able to give all orders that he would like to give but only just a few of them that he remebered from recent training. Each of them refered to a 'line' leading through a sequence of important strategic positions; if such an order is given, then each army unit in the line moves forward to the next position along the line. Every line is really a cycle, so after the movement is performed there is also a single army unit in every strategic position.

Bytor ordered his spies to find the locations of the Qbits' army units. When the spies come back, there will be only about half an hour to the start of the battle. During this period of time, Bytor will need to give all necessary orders to get all his army units to proper positions. This amount of time will be enough for a moment of thought and performing at most 10 orders. Bytor called for his computer scientists and asked them to write a program that, given the initial and requested army arrangements, checks whether there exists a sequence of orders that is short enough and leads from the initial to the final arrangement.

The first line of the input contains two integers n and m (2 ≤ n ≤ 75, 1 ≤ m ≤ 10), separated by a single space. n represents the number of strategic positions and m is equal to the number of lines.

The second line contains a single m-letter word composed only of small English letters. The i-th letter describes the type of unit located in the i-th strategic point due to the old Bytean military code. There can be several units having the same code in the fort.

The third line also contains an n-letter word. It describes the unit types that should be located in strategic positions 1, 2, …, n after the movement. This word will be different from the previous one.

Each of the following m lines contains a description of a line having the form: c, a₁, a₂, …, a_c (the numbers separated by single spaces). The first number (c) denotes the number of strategic positions in the line. The number a₁ (1 ≤ a_i ≤ n for 1 ≤ i ≤ c) describes the number of the i-th strategic point in the line. All numbers  in a single line will be different. Performing such an order causes the following movement of army units: a₁ -> a₂, a₂ -> a₃, ..., a_c-1 -> a_c, a_c -> a₁.

If it is impossible to obtain the final arrangement within 10 orders, your program should output one word NIE (Polish for no). In the opposite case your program should output at most 10 space-separated numbers of lines (between 1 and m), that Bytor should move in his respective orders. If there are multiple correct solutions, your program should output the one that requires the least number of orders. If there are still multiple solutions, your program should output the lexicographically first (if t is the first position where two solutions of equal length differ, then the first of them is lexicographically smaller than the second one if the t-th order in the first solution has smaller line number than the t-th order in the second solution).