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

Poveste şi cerinţă...

Ai un prieten care ia momentan un curs de Automate Finite si vorbeste intr-una despre asta. Multa vreme ai crezut ca nu e un curs foarte legitim, fiindca prietenul tau vorbea despre automate care "tolereaza" cuvinte, pe cand stim cu totii ca formularea consacrata este "accepta". Astazi insa, prietenul tau ti-a definit mai exact "toleranta" si, ce-i drept, e relativ interesant.
 
Spunem ca un 'Automat Finit Determinist':https://en.wikipedia.org/wiki/Deterministic_finite_automaton (prescurtat AFD) *tolereaza* stringul $X$ daca si numai daca exista un string $Y$ astfel incat $X$ este subsir de-al lui $Y$, iar $Y$ este acceptat de AFD in sensul clasic.
 
Dandu-ti-se un AFD esti curios cat de densa este multimea stringurilor tolerate de acesta relativ la multimea tuturor stringurilor peste alfabetul automatului. Mai formal, esti curios daca limita raportului dintre numarul de stringuri tolerate si numarul total de stringuri posibile (care, pentru o anumita lungime fixa $L$, sunt in numar de $SIGMA^L^$) cand lungimea acestora tinde la infinit este strict pozitiva.

h2. Date de intrare

Fişierul de intrare $density.in$ ...

Fişierul de intrare $density.in$ va contine pe prima sa linie numarul de teste, $T$. Structura unui test este urmatoarea: Pe prima linie se vor afla valorile $N SIGMA F$, reprezentand numarul de stari ale automatului, marimea alfabetului utilizat de catre automat, respectiv numarul de stari finale ale automatului. Urmeaza o linie cu $F$ valori distincte din multimea ${1, 2, .. N}$, reprezentand multimea starilor finale ale automatului. Urmeaza apoi $N$ linii, fiecare continand cate $SIGMA$ valori din multimea ${1, 2, .. N}$. Al $j$-lea element de pe linia $i$ indica destinatia tranzitiei asociate caracterului cu numarul $j$ din starea $i$.

h2. Date de ieşire

În fişierul de ieşire $density.out$ ...

În fişierul de ieşire $density.out$ se vor afla $T$ linii, fiecare continand raspunsul pentru testul corespunzator. Daca limita descrisa in enunt este strict mai mare decat $0$, raspunsul este "DA". Altfel, raspunsul este "NU".

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 10.000$
* $1 ≤ SIGMA ≤ 26$
* Starea de inceput este tot timpul starea cu numarul $1$.
* Pentru $90$ de teste $1 ≤ N ≤ 1.000$.

h2. Exemplu
table(example). |_. density.in |_. density.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
1 1 1
1
1
3 1 2
1 2
2
3
3
| DA
NU

|
h3. Explicaţie

...

Primul automat tolereaza orice sir format din primul si unicul caracter al alfabetului. Deci densitatea sa este $1$.
In cazul celui de-al doilea automat, alfabetul este acelasi, insa automatul tolereaza doar sirurile de lungime mai mica sau egala cu $2$. Este clar ca densitatea sa este egala cu $0$

== include(page="template/taskfooter" task_id="density") ==