drumuri3

Drumuri3

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

Fie un graf neorientat cu N (1 <= N <= 70) noduri. Definim un drum un graf o secventa de noduri a1, a2, ... an a.i sa existe muchia (ai, ai + 1), i = 1, n - 1. Astfel, orice nod poate fi folosit de oricate ori intr-un drum, la fel ca si orice muchie. Definim lungimea unui drum ca fiind numarul de noduri din drumul respectiv.
Se cere sa se afle numarul de drumuri ce incep in nodul i, se termina in nodul j, cu conditia ca i < j iar lungimea drumurilor sa fie <= K.

Bercea tocmai şi-a procurat (prin mijloace îndoielnice) o nouă limuzină. Acum, pentru a arăta tuturor noua sa achiziţie, el s-a hotărât să facă o plimbare prin oraş, oraşul fiind de fapt un graf cu $N$ noduri şi $M$ muchii. Un drum se defineşte ca fiind o secvenţă de noduri $a{~1~}$, $a{~2~}$, ..., $a{~k~}$ astfel încât să existe muchia ({$a{~i~}$}, $a{~i+1~}$), oricare ar fi $1$ ≤ $i$ ≤ $k-1$. Astfel orice nod poate fi folosit de oricâte ori într-un drum, la fel şi orice muchie. Lungimea unui drum este numărul de noduri care fac parte din drumul respectiv.
Totuşi Bercea nu doreşte să facă drumuri mai lungi de $K$ noduri, deoarece atunci ar putea ieşi din sfera sa de influenţă din oraş. Aşadar, fiind date două noduri $i$ si $ji$, aflaţi numărul de drumuri care încep în nodul $i$, se termină in nodul $ji$, iar lungimea fiecărui drum este ≤ $K$.
 

h2. Date de intrare