== include(page="template/taskheader" task_id="teroristi") ==
Poveste şi cerinţă...
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.
h2. Cerinta
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.
h2. Date de intrare
Fişierul de intrare $teroristi.in$ ...
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 din 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.
h2. Date de ieşire
În fişierul de ieşire $teroristi.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000 000$
* $1 ≤ 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.
h2. Exemplu
table(example). |_. teroristi.in |_. teroristi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
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*$
== include(page="template/taskfooter" task_id="teroristi") ==
