Se consideră un graf orientat cu n vârfuri, numerotate de la 1 la n, şi m arce. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de arce al unui drum elementar care are ca extremitate inițială vârful x și ca extremitate finală vîrful y.

Cerinţa

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța minimă dintre x și y.

Date de intrare

Fişierul de intrare dmin2.in conţine pe prima linie două numere n şi m, reprezentând numărul de noduri, respectiv numărul de arce. Fiecare dintre următoarele m linii va conţine câte două numere x şi y, separate printr-un spaţiu, cu semnificaţia: există arc de la nodul x la nodul y.

Următoarea linie conține un număr k, iar următoarele k linii câte două numere x y.

Date de ieşire

Fişierul de ieşire dmin2.out va conţine k linii. Fiecare linie va conține distața minimă dintre nodurile x y din fișierul de intrare, în ordinea din fișierul de intrare. Dacă pentru perechea x y nu există un drum elementar de la x la y, atunci pe linia corespunzătoare se va afișa valoarea -1.

Restricţii şi precizări

• n ≤ 100
• k ≤ 100

Exemplu:

dmin2.in

6 7
1 3
1 2
2 3
2 4
3 4
4 5
5 6
3
1 6
5 3
2 5

dmin2.out

4
-1
2