#include <array>
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct disjoint_set {
  vector<int> p, sz;
  disjoint_set(int n) {
    p.assign(n, -1); sz.assign(n, 1); 
  }
  int find(int x) {
    return p[x] < 0 ? x : (p[x] = find(p[x]));
  }
  int getsz(int x) {
    return sz[find(x)];
  }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(sz[x] > sz[y]) swap(x, y);
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
};

int main() {
  int n, q;
  cin >> n >> q;
  disjoint_set dsu(n);
  vector<vector<int>> edges(n);
  auto bfs = [&](vector<int>& dp, int src) -> int {
    dp.assign(n, 1e9);
    int ret = src;
    queue<int> q;
    q.push(src);
    dp[src] = 0;
    while(q.size()) {
      ret = q.front(); q.pop();
      for(int out: edges[ret]) {
        if(dp[out] > dp[ret] + 1) {
          dp[out] = dp[ret] + 1;
          q.push(out);
        }
      }
    }
    return ret;
  };
  for(int i = 0; i < n-3; i++) {
    int a, b;
    cin >> a >> b; a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
    assert(dsu.merge(a, b));
  }
  vector<int> ids;
  vector<int> treediam;
  vector<array<int, 2>> diameters;
  vector<vector<int>> distances;
  for(int i = 0; i < n; i++) {
    bool present = false;
    for(int out: ids) present = present || dsu.find(i) == out;
    if(present) continue;
    ids.push_back(dsu.find(i));
    vector<int> ignoredp, adp, bdp;
    int a = bfs(ignoredp, i);
    int b = bfs(adp, a);
    int c = bfs(bdp, b);
    treediam.push_back(bdp[c]);
    diameters.push_back({a, b});
    distances.push_back(adp);
    distances.push_back(bdp);
  }
  assert(ids.size() == 3);
  while(q--) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    int asrc = 0, bsrc = 0;
    while(dsu.find(a) != ids[asrc]) asrc++;
    while(dsu.find(b) != ids[bsrc]) bsrc++;
    assert(asrc != bsrc);
    int csrc = 3 - asrc - bsrc;
    cout << (
      1 + max(distances[2*asrc][a], distances[2*asrc+1][a]) + 
      1 + max(distances[2*bsrc][b], distances[2*bsrc+1][b]) + 
      1 + treediam[csrc]
    ) << "\n";
  }
}