Se consideră un graf neorientat conex cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu 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 dmin.in conţine pe prima linie două numere n şi m, reprezentând numărul de noduri, respectiv numărul de muchii. 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ă o muchie între nodul x şi 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 dmin.out va conţine k linii. Fiecare linie va conține distanța minimă dintre nodurile x y din fișierul de intrare, în ordinea din fișierul de intrare.

Restricţii şi precizări

• n ≤ 100
• k ≤ 100
• pentru toate perechile x y există cel puțin un drum elementar de la x la y.

Exemplu:

dmin.in

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

dmin.out

4
2
2