바이토르 장군

Qbits(큐비트) 군대가 쳐들어온다!

바이트모어 요새의 총사령관 바이토르 장군은 갑자기 잠에서 깨어 본부로 달려가 작전 계획을 확인했다. 상황은 좋지 않았다. 요새의 각 전략 요충지에는 부대가 하나씩 배치되어 있지만, 일부 부대는 잘못된 위치에 있었다. 게다가 명령을 내리는 데 큰 문제가 생겼다. Qbits의 비밀 요원들이 양자 순간이동으로 요새의 암호 담당자들을 모두 납치했기 때문이다. 이제 장군은 최근 훈련에서 외워 둔 몇 가지 명령만 내릴 수 있다.

각 명령은 여러 전략 요충지를 잇는 하나의 라인(line)에 대응한다. 어떤 명령을 내리면, 그 라인에 속한 모든 부대가 라인을 따라 다음 요충지로 한 칸씩 전진한다. 각 라인은 사실 하나의 순환(cycle)이므로, 이동을 마친 뒤에도 모든 요충지에는 정확히 부대 하나가 남는다.

전투 시작까지는 약 30분이 남았고, 이 시간 동안 장군은 최대 10개의 명령만 내릴 수 있다. 초기 배치와 목표 배치가 주어질 때, 초기 배치를 목표 배치로 바꾸는 충분히 짧은 명령 순서가 존재하는지 판정하고, 존재한다면 그 명령 순서를 구하는 프로그램을 작성하라.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다 ($2 \le n \le 75$, $1 \le m \le 10$). $n$은 전략 요충지의 수, $m$은 라인의 수이다.

둘째 줄에는 $n$개의 영어 소문자로 이루어진 단어가 주어진다. $i$번째 글자는 현재 $i$번째 요충지에 배치된 부대의 종류(옛 바이트 군사 부호)를 나타낸다. 같은 종류의 부대가 여러 개 있을 수 있다.

셋째 줄에도 $n$개의 소문자로 이루어진 단어가 주어지며, 이동을 마친 뒤 요충지 $1, 2, \dots, n$에 놓여야 하는 부대의 종류를 나타낸다. 이 단어는 둘째 줄의 단어와 다르다.

이어지는 $m$개의 줄에는 각 라인의 정보가 $c\; a_1\; a_2\; \dots\; a_c$ 형식으로 (공백으로 구분되어) 주어진다. 첫 수 $c$는 그 라인에 포함된 요충지의 개수이고, $a_i$ ($1 \le a_i \le n$)는 라인의 $i$번째 요충지 번호이다. 한 줄 안의 번호는 모두 서로 다르다. 이 명령을 내리면 부대는 다음과 같이 이동한다: $a_1 \to a_2,\; a_2 \to a_3,\; \dots,\; a_{c-1} \to a_c,\; a_c \to a_1$.

10개 이하의 명령으로 목표 배치를 만들 수 없으면 NIE(폴란드어로 "아니오")를 한 줄에 출력한다.

만들 수 있으면, 장군이 차례로 내려야 할 라인 번호($1$ 이상 $m$ 이하)를 공백으로 구분하여 최대 10개까지 출력한다. 정답이 여러 개이면 명령 수가 가장 적은 것을 출력하고, 그래도 여러 개이면 사전순으로 가장 앞서는 것을 출력한다. (길이가 같은 두 해에서 처음으로 달라지는 위치를 $t$라 할 때, $t$번째 명령의 라인 번호가 더 작은 해가 사전순으로 더 앞선다.)