<PREV Problem:
Solved by 19 users: Jacob, rem, rvashegin, WsemirZ, wInuX, tourist, Zhukov_Dmitry, dan, zloy_mipt, JohnJones_001, mazahaka, MIKseR, UdH-WiNGeR, RAVEman, defrager, fetetriste, EAA2008, ripatti, Dest.

General Bytor

Time limit = 3 second(s)

Memory limit = 128Mb

'Qbits are coming!'

General Bytor, the commander-in-chief of Fort Bytemore, woke up, quickly went to the headquarters and looked at the operational plan. Unfortunately the situation didn't look well. In every important strategic position there was one army unit of the Fort; however some units were located at incorrect positions. Even worse, it appeared that there would be huge problems with giving orders. The reason for that was that Qbits' secret agents used quantum teleportation techniques to kidnap all cryptographers from Bytemore! Without them, Bytor won'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 refers to a 'line' leading through a sequence of important strategic positions; if such an order is given, then each army unit on 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 only remain about half an hour to the beginning 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 needed 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 file contains two integers n and m (2<=n<=75, 1<=m<=10), separated by a single space. n denotes the number of strategic positions and m is equal to the number of lines.

The second line contains a single n-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 a n-letter word. It describes the unit types that should be located in strategic positions 1, 2, ..., n after the movement. The second word will be different from the first one.

Each of the following m lines contains a description of a 'line' in the form: c, a1, a2, ..., ac (the numbers are separated by single spaces). The first number (c) denotes the number of strategic positions in the 'line'. Number ai (1<=ai<=n for 1<=i<=c) describes the number of the i-th strategic point in the line.

All numbers ai in a single line will be different. Performing such an order causes the following movement of army units: a1 → a2, a2 → a3, ... , a_(n-1) → an, an → a1.


If the final arrangement cannot be obtained within 10 orders, your program should output one word IMPOSSIBLE. In the opposite case your program should output at most 10 space-separated numbers of 'lines' (between 1 and m), that should be moved in succeeding Bytor's 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 lenght differ, then the first of them is lexicographically smaller than the second one iff the t-th order in the first solution has smaller line number than the t-th order in the second solution).

12 6
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
1 2 2 3 3 6 1

Eryk Kopczynski (Eryx)

<PREV | Problem set | Search related messages | NEXT>

© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID =