Al

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

class Graph
{
private :

    int V;
    list <int> *adj;

public :

    Graph(int V);
    void Add_Edge(int u, int v);
    void BFS(int src, vector <int> &D);
};

inline Graph::Graph(int V)
{
    this->V = V;
    adj = new list <int> [V + 1];
}

inline void Graph::Add_Edge(int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

inline void Graph::BFS(int src, vector <int> &D)
{
    queue <int> Q;
    D[src] = 0;
    Q.push(src);

    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();

        for (auto v : adj[u])
            if (D[v] == INF)
                D[v] = D[u] + 1, Q.push(v);
    }
}

int n, m, k;

int main()
{
    fin >> n >> m;
    vector <vector <int> > D(n + 1, vector <int> (n + 1, INF));
    Graph G(n);

    for (int i = 1, u, v; i <= m; ++i)
        fin >> u >> v, G.Add_Edge(u, v);

    for (int i = 1; i <= n; ++i)
        G.BFS(i, D[i]);

    fin >> k;
    for (int i = 1, u, v; i <= k; ++i)
        fin >> u >> v, fout << D[u][v] << '\n';

    return 0;
}