nrcuv

Lista lui Andrei

== include(page="template/taskheader" task_id="nrcuv") ==

==Include(page="template/taskheader" task_id="nrcuv")==

Poveste ...
h2. Cerinta
 
...

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. Restrictii

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

| nrcuv.in | nrcuv.out |
| linia1
linia2
linia3
| linia1
linia2
|

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") ==

==Include(page="template/taskfooter" task_id="nrcuv")==
 
 

847