Inspiraţi de faimoasa grupare Al-Qaeda, teroriştii din oraşul Tomis s-au hotărât să saboteze Olimpiada Naţională de Informatică. Pentru a-şi pune planul în aplicare ei au răpit-o pe Miruna şi au trimis o scrisoare concurenţilor în care cer o răscumpărare foarte mare. Ca măsură de siguranţă, scrisoarea nu a fost scrisă de mână, ci a fost compusă lipind pe o foaie litere decupate dintr-un ziar. Detectivul Mirunel are un plan pentru a determina identitatea teroriştilor. Primul lucru pe care vrea să îl facă Mirunel este să demonstreze că teroriştii citesc Dilema veche. Detectivul are ultimul număr al revistei şi vrea să ştie dacă scrisoarea teroriştilor putea fi scrisă decupând litere doar din această ediţie. Din păcate sarcina este prea grea pentru Mirunel, deoarece atunci când decupează o bucată dintr-un ziar, aceasta va conţine 2 litere, câte una pe fiecare faţă. Fiecare bucată de ziar poate fi utilizată în două moduri, în funcţie de litera care va fi folosită la reconstituirea scrisorii trimise, iar acest lucru l-a încurcat de tot pe Mirunel.
Cerinţă
Scrieţi un program care să determine o modalitate validă de reconstituire a scrisorii trimise de terorişti, folosind doar bucăţile de ziar decupate de Mirunel.
Date de intrare
Fişierul de intrare teroristi.in conţine pe prima linie două numere naturale n şi m, reprezentând lungimea scrisorii trimise de terorişti, respectiv numărul de bucăţi de ziar decupate. Pe a doua linie se află mesajul scrisorii sub forma unui şir de n litere mici aparţinând alfabetului englez. Fiecare dintre următoarele m linii conţine exact 2 caractere din alfabetul englez separate prin spaţiu, reprezentând literele înscrise pe cele două feţe ale unei bucăţi de ziar.
Date de ieşire
Fişierul de ieşire teroristi.out va conţine o singură linie pe care se va găsi un şir de n numere distincte din mulţimea {1, 2, ... m}. Pe poziţia i din şirul afişat se va afla indicele bucăţii de ziar (în ordinea în care acestea apar în fişierul de intrare) folosite pentru a reprezenta cea de a i-a literă din scrisoare.
Restricţii
1 ≤ n ≤ 1 000 000
n ≤ m ≤ 1 000 000
Pentru 10% din teste n, m = 3
Pentru alte 10% din teste n, m ≤ 15
Pentru alte 30% din teste n, m ≤ 1000
Dacă există mai multe soluţii, poate fi afişată oricare dintre ele.
Se garantează că pe datele de test există întotdeauna soluţie.
Exemple
teroristi.in
teroristi.out
Explicaţii
6 8
miruna
b a
m i
f a
u g
f m
a g
b r
n a
5 2 7 4 8 3
Se vor folosi următoarele bucăţi: 5 – f m
2 – m i
7 – b r
4 – u g
8 – n a
3 – f a