h2. Date de intrare

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.

Fişierul de intrare $drumuri3.in$ va conţine pe prima linie numerele naturale $N$, $M$, $K$, $i$ şi $ji$ 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.

h2. Date de ieşire

În fişierul de ieşire $drumuri3.out$ se vor afişa $Q$ linii cu numerele dorite modulo $10 007$.

În fişierul de ieşire $drumuri3.out$ se va afişa pe o singură linie numărul dorit modulo $10 007$.

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.

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

| 6 15 4 2

| 6 15 4 1 2

1 2
1 3
1 4

4 5
4 6
5 6

1 2
1 6
| 26
26
|

| 26 |

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

5300