#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110000;
int n, m;
vector<int> e[MAXN];
int p[MAXN], sz[MAXN], nxt[MAXN], hvp[MAXN], q[MAXN];
int incy[MAXN], pos[MAXN];
int stc;
vector<int> cycle;
struct sNode {
  int a, b;
  int d, mark;
  int lc, rc;
};
int tl;
sNode t[MAXN * 6];
int Create(int a, int b) {
  int z = tl++, mid = (a + b) >> 1;
  t[z].a = a;
  t[z].b = b;
  t[z].d = 0;
  t[z].mark = 0;
  t[z].lc = t[z].rc = 0;
  if (a < b) {
    t[z].lc = Create(a, mid);
    t[z].rc = Create(mid + 1, b);
    t[z].d = t[t[z].lc].d + t[t[z].rc].d;
  } else {
    t[z].d = 0;
  }
  return z;
}
inline void Inverse(const int z) { t[z].d = t[z].b - t[z].a + 1 - t[z].d; }
void Inverse(int z, int a, int b) {
  if (a <= t[z].a && t[z].b <= b) {
    Inverse(z);
    t[z].mark = 1 - t[z].mark;
    return;
  }
  if (t[z].mark) {
    if (t[z].lc) {
      Inverse(t[z].lc);
      Inverse(t[z].rc);
      t[t[z].lc].mark = 1 - t[t[z].lc].mark;
      t[t[z].rc].mark = 1 - t[t[z].rc].mark;
    }
    t[z].mark = 0;
  }
  if (a <= t[t[z].lc].b) Inverse(t[z].lc, a, b);
  if (t[t[z].rc].a <= b) Inverse(t[z].rc, a, b);
  t[z].d = t[t[z].lc].d + t[t[z].rc].d;
}
int GetNum(int z, int a, int b) {
  if (a <= t[z].a && t[z].b <= b) return t[z].d;
  if (t[z].mark) {
    if (t[z].lc) {
      Inverse(t[z].lc);
      Inverse(t[z].rc);
      t[t[z].lc].mark = 1 - t[t[z].lc].mark;
      t[t[z].rc].mark = 1 - t[t[z].rc].mark;
    }
    t[z].mark = 0;
  }
  int ans = 0;
  if (a <= t[t[z].lc].b) ans += GetNum(t[z].lc, a, b);
  if (t[t[z].rc].a <= b) ans += GetNum(t[z].rc, a, b);
  return ans;
}
void FindCycle() {
  int qh = 0, ql = 0, x, y, z;
  memset(p, 0xff, sizeof(p));
  memset(incy, 0, sizeof(incy));
  cycle.clear();
  q[ql++] = 0;
  for (qh = 0; qh < ql; qh++) {
    z = q[qh];
    for (int i = 0; i < e[z].size(); i++) {
      x = e[z][i];
      if (x == p[z]) continue;
      if (p[x] == -1) {
        q[ql++] = x;
        p[x] = z;
      } else {
        for (y = z; y != 0 && y != x; y = p[y]) incy[y] = 1;
        incy[0] = 1;
        for (y = x; !incy[y]; y = p[y])
          ;
        for (int k = z; k != y; k = p[k]) cycle.push_back(k);
        reverse(cycle.begin(), cycle.end());
        for (int k = x; k != y; k = p[k]) cycle.push_back(k);
        cycle.push_back(y);
        qh = ql - 1;
        break;
      }
    }
  }
  memset(incy, 0xff, sizeof(incy));
  for (int i = 0; i < cycle.size(); i++) incy[cycle[i]] = i;
}
void CreateOuterTree() {
  tl = 0;
  Create(1, n);
  int qh, ql, x, y, z, sp = 0;
  memset(p, 0xff, sizeof(p));
  memset(sz, 0, sizeof(sz));
  memset(nxt, 0xff, sizeof(nxt));
  memset(pos, 0, sizeof(pos));
  for (int v = 0; v < cycle.size(); v++) {
    ql = 0;
    q[ql++] = cycle[v];
    for (qh = 0; qh < ql; qh++) {
      z = q[qh];
      for (int i = 0; i < e[z].size(); i++) {
        x = e[z][i];
        if (incy[x] >= 0 || p[z] == x) continue;
        p[x] = z;
        q[ql++] = x;
      }
    }
    for (int k = ql - 1; k >= 0; k--) {
      z = q[k];
      sz[z]++;
      for (int i = 0; i < e[z].size(); i++) {
        x = e[z][i];
        if (p[x] == z) sz[z] += sz[x];
      }
    }
    for (int k = 0; k < ql; k++) {
      z = q[k];
      for (int i = 0; i < e[z].size(); i++) {
        x = e[z][i];
        if (p[x] != z) continue;
        if (nxt[z] == -1 || sz[x] > sz[nxt[z]]) nxt[z] = x;
      }
    }
    hvp[q[0]] = q[0];
    for (int k = 1; k < ql; k++) {
      z = q[k];
      if (nxt[p[z]] == z)
        hvp[z] = hvp[p[z]];
      else
        hvp[z] = z;
    }
    for (int k = 1; k < ql; k++) {
      if (pos[z = q[k]] != 0) continue;
      for (y = z; y >= 0; y = nxt[y]) pos[y] = ++sp;
    }
  }
  stc = sp;
  for (int i = 0; i < cycle.size(); i++) pos[cycle[i]] = ++sp;
}
int ProcessNodeInTree(int node) {
  int z;
  for (z = node; incy[z] < 0;)
    if (hvp[z] == z) {
      Inverse(0, pos[z], pos[z]);
      z = p[z];
    } else {
      Inverse(0, pos[nxt[hvp[z]]], pos[z]);
      z = hvp[z];
    }
  return z;
}
int Query(int a, int b) {
  a = ProcessNodeInTree(a);
  b = ProcessNodeInTree(b);
  if (a != b) {
    int aa, bb, len, cs = cycle.size();
    aa = incy[a], bb = incy[b];
    len = abs(aa - bb);
    if (aa < bb) {
      if (len * 2 < cs ||
          (len * 2 == cs && cycle[aa + 1] < cycle[(aa + cs - 1) % cs]))
        Inverse(0, pos[cycle[aa + 1]], pos[cycle[bb]]);
      else {
        Inverse(0, stc + 1, pos[cycle[aa]]);
        if (bb < cs - 1) Inverse(0, pos[cycle[bb + 1]], n);
      }
    } else {
      if (len * 2 < cs ||
          (len * 2 == cs && cycle[aa - 1] < cycle[(aa + 1) % cs]))
        Inverse(0, pos[cycle[bb + 1]], pos[cycle[aa]]);
      else {
        Inverse(0, stc + 1, pos[cycle[bb]]);
        if (aa < cs - 1) Inverse(0, pos[cycle[aa + 1]], n);
      }
    }
  }
  int v1 = stc == 0 ? 0 : GetNum(0, 1, stc), v2 = GetNum(0, stc + 1, n);
  return n - v1 - min(v2, (int)cycle.size() - 1);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) e[i].clear();
  for (int i = 0, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    x--;
    y--;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  FindCycle();
  CreateOuterTree();
  for (int mm = 0, aa, bb; mm < m; mm++) {
    scanf("%d%d", &aa, &bb);
    printf("%d\n", Query(aa - 1, bb - 1));
  }
  return 0;
}
