== 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) $Q$ limuzine. Acum, pentru a arăta tuturor noile sale achiziţii, el s-a hotărât să facă mai multe plimbări prin oraş, oraşul fiind de fapt un graf *neorientat* 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 $Q$ perechi de 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$.
Deoarece numărul de drumuri poate fi foarte mare şi Bercea nu ştie să numere decât până la câte milioane de € are, afişaţi răspunsul modulo $10 007$.
h2. Date de intrare
Fişierul de intrare $drumuri3.in$ ...
Fişierul de intrare $drumuri3.in$ va conţine pe prima linie numerele naturale $N$, $M$, $K$ şi $Q$ cu semnificaţia de mai sus. Următoarele $M$ linii vor conţine câte două numere naturale reprezentând două noduri între care există o muchie. Următoarele $Q$ linii vor conţine câte două numere naturale $i$ şi $ji$ reprezentând perechile de oraşe între care Bercea doreşte să se plimbe.
h2. Date de ieşire
În fişierul de ieşire $drumuri3.out$ ...
În fişierul de ieşire $drumuri3.out$ se vor afişa $Q$ linii cu numerele dorite modulo $10 007$.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100$
* $1 ≤ K ≤ 5 000$
* $1 ≤ Q ≤ 2 500$
* Graful este conex (există cel puţin un drum între oricare două perechi de noduri).
* O muchie nu va apărea în fişierul de intrare de mai multe ori.
* Nu va exista în fişierul de intrare o muchie de la un nod la el însuşi.
* $i$ ≠ $ji$
h2. Exemplu
table(example). |_. drumuri3.in |_. drumuri3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 15 4 2
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 2
1 6
| 26
26
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="drumuri3") ==
