==Include(page="template/taskheader" task_id="nrcuv")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Lista lui Andrei
 
 
 
Fiind foarte pasionat de civilizatiile extraterestre, Andrei a inceput sa studieze limba martienilor pentru a putea comunica usor cu ei atunci cand va fi cazul. Oricat s-a documentat el a putut afla doar ca toate cuvintele acestei limbi contin N litere mici din alfabetul englez si a mai gasit o lista cu perechi de litere ce nu pot aparea pe pozitii vecine intr-un cuvant. Pentru ca are de gand sa studieze fonetica fiecarui cuvant posibil in parte, Andrei ar vrea mai intai sa vada cat de voluminoasa este munca pe care si-o propune si va roaga sa determinati cate cuvinte poate avea limba.
 
h2. Cerinta
 
Determinati cate cuvinte de lungime N se pot forma folosind doar litere mici ale alfabetului englez astfel incat oricare doua litere care formeaza o pereche in lista lui Andrei sa nu se afle pe pozitii vecine.
 
h2. Date de Intrare
 
Pe prima linie a fisierului nrcuv.in se afla numerele intregi N si M, reprezentand numarul de litere din care este format un cuvant si numarul de perechi din lista lui Andrei. Urmatoarele M linii contin o pereche de forma "l[1] l[2]" unde l[1] si l[2] sunt litere mici ale alfabetului englez.
 
h2. Date de Iesire
 
Fisierul nrcuv.out contine pe prima linie numarul cerut modulo 104659.
 
h2. Restrictii si precizari
 
&#159; 1 <= N <= 1000
 
&#159; 0 <= M <= 2000
 
&#159; pot exista perechi simetrice sau identice in lista
 
&#159; doua pozitii sunt vecine daca modulul diferentei lor este 1
 
h2. Exemplu
 
 
 
nrcuv.in nrcuv.out
2 7 667
 
a a
 
a b
 
b c
 
c d
 
c f
 
b a
 
c f
 

==Include(page="template/taskheader" task_id="nrcuv")==
 
 
Fiind foarte pasionat de civilizatiile extraterestre, Andrei a inceput sa studieze limba martienilor pentru a putea comunica usor cu ei atunci cand va fi cazul. Oricat s-a documentat el a putut afla doar ca toate cuvintele acestei limbi contin $N$ litere mici din alfabetul englez si a mai gasit o lista cu perechi de litere ce nu pot aparea pe pozitii vecine intr-un cuvant. Pentru ca are de gand sa studieze fonetica fiecarui cuvant posibil in parte, Andrei ar vrea mai intai sa vada cat de voluminoasa este munca pe care si-o propune si va roaga sa determinati cate cuvinte poate avea limba.
 
h2. Cerinta
 
Determinati cate cuvinte de lungime $N$ se pot forma folosind doar litere mici ale alfabetului englez astfel incat oricare doua litere care formeaza o pereche in lista lui Andrei sa nu se afle pe pozitii vecine.
 
h2. Date de intrare
 
Pe prima linie a fisierului $nrcuv.in$ se afla numerele intregi $N$ si $M$, reprezentand numarul de litere din care este format un cuvant si numarul de perechi din lista lui Andrei. Urmatoarele $M$ linii contin o pereche de forma "$l{~1~} l{~2~}$" unde $l{~1~}$ si $l{~2~}$ sunt litere mici ale alfabetului englez.
 
h2. Date de iesire
 
Fisierul $nrcuv.out$ contine pe prima linie numarul cerut modulo $104659$.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 1000$
* $0 ≤ M ≤ 2000$
* Pot exista perechi simetrice sau identice in lista
* Doua pozitii sunt vecine daca modulul diferentei lor este $1$
 
h2. Exemplu
 
table(example). |_. nrcuv.in |_. nrcuv.out |
| 2 7
a a
a b
b c
c d
c f
b a
c f
| 667 |
 
==Include(page="template/taskfooter" task_id="nrcuv")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/nrcuv/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="nrcuv")==

847