Fişierul intrare/ieşire:nrcuv.in, nrcuv.outSursăpreONI 2006 Runda 4
AutorDaniel PasailaAdăugată de
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

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.

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 "l1 l2" unde l1 si l2 sunt litere mici ale alfabetului englez.

Date de iesire

Fisierul nrcuv.out contine pe prima linie numarul cerut modulo 104659.

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

Exemplu

nrcuv.innrcuv.out
2 7
a a
a b
b c
c d
c f
b a
c f
667
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content