#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
vector<int> side[maxn], cir, idx[maxn];
bool incir[maxn], vis[maxn];
int stk[maxn], stktop, top[maxn], heavy[maxn], size[maxn], dfn_cnt, dfn[maxn],
    f[maxn][20], dep[maxn], cirid[maxn];
struct segment_tree {
  int sum[maxn << 2], tag[maxn << 2];
  void push_up(int rt) { sum[rt] = sum[(rt << 1)] + sum[(rt << 1 | 1)]; }
  void push_down(int rt, int l, int r) {
    if (tag[rt]) {
      int mid = (l + r) >> 1;
      tag[(rt << 1)] ^= 1;
      sum[(rt << 1)] = (mid - l + 1) - sum[(rt << 1)];
      tag[(rt << 1 | 1)] ^= 1;
      sum[(rt << 1 | 1)] = (r - (mid + 1) + 1) - sum[(rt << 1 | 1)];
      tag[rt] = 0;
    }
  }
  void upd(int l, int r, int rt, int tl, int tr) {
    if (tl <= l && r <= tr) {
      tag[rt] ^= 1;
      sum[rt] = (r - l + 1) - sum[rt];
      return;
    }
    push_down(rt, l, r);
    int mid = (l + r) >> 1;
    if (tl <= mid) upd(l, mid, (rt << 1), tl, tr);
    if (tr >= mid + 1) upd(mid + 1, r, (rt << 1 | 1), tl, tr);
    push_up(rt);
  }
  int query(int l, int r, int rt, int tl, int tr) {
    if (tl <= l && r <= tr) return sum[rt];
    push_down(rt, l, r);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (tl <= mid) ans += query(l, mid, (rt << 1), tl, tr);
    if (tr >= mid + 1) ans += query(mid, r, (rt << 1 | 1), tl, tr);
    return ans;
  }
} t, loop;
int LCA(int u, int v) {
  if (dep[v] < dep[u]) swap(u, v);
  for (int i = 19; i >= 0; i--)
    if (dep[f[u][i]] >= dep[v]) u = f[u][i];
  if (u == v) return u;
  for (int i = 19; i >= 0; i--)
    if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
  return f[u][0];
}
void dfs1(int u, int S) {
  vis[u] = 1;
  stk[++stktop] = u;
  for (int i = 0; i < side[u].size(); i++) {
    int v = side[u][i];
    if (idx[u][i] == S) continue;
    if (!vis[v])
      dfs1(v, idx[u][i]);
    else {
      if (cir.size())
        continue;
      else {
        cir.push_back(v);
        incir[v] = 1;
        for (int j = stktop; j && stk[j] != v; j--)
          cir.push_back(stk[j]), incir[stk[j]] = 1;
      }
    }
  }
  stktop--;
}
void dfs2(int u, int fa) {
  size[u] = 1;
  f[u][0] = fa;
  for (int i = (1), iend = (19); i <= iend; i++)
    f[u][i] = f[f[u][i - 1]][i - 1];
  dep[u] = dep[fa] + 1;
  for (int i = 0; i < side[u].size(); i++) {
    int v = side[u][i];
    if (v == fa || incir[v]) continue;
    dfs2(v, u);
    if (size[v] > size[heavy[u]]) heavy[u] = v;
  }
}
int fincir[maxn];
void dfs3(int u, int Top) {
  top[u] = Top;
  dfn[u] = ++dfn_cnt;
  if (heavy[u]) dfs3(heavy[u], Top);
  for (int i = 0; i < side[u].size(); i++) {
    int v = side[u][i];
    if (v == f[u][0] || incir[v]) continue;
    if (v != heavy[u]) dfs3(v, v);
  }
}
int n, m;
int jump(int u) {
  while (1) {
    t.upd(1, n, 1, dfn[top[u]], dfn[u]);
    u = top[u];
    if (!f[u][0]) break;
    u = f[u][0];
  }
  return fincir[u];
}
vector<int> st;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1), iend = (n); i <= iend; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    side[u].push_back(v);
    idx[u].push_back(i);
    side[v].push_back(u);
    idx[v].push_back(i);
  }
  dfs1(1, 0);
  memset(vis, 0, sizeof(vis));
  stktop = 0;
  for (int i = 0; i < cir.size(); i++) {
    int u = cir[i];
    cirid[u] = i;
    for (int j = 0; j < side[u].size(); j++) {
      int v = side[u][j];
      if (incir[v]) continue;
      st.push_back(v);
      fincir[v] = u;
    }
  }
  for (int i = 0; i < st.size(); i++) {
    int v = st[i];
    dfs2(v, 0);
    dfs3(v, v);
  }
  for (int i = (1), iend = (m); i <= iend; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    int lca = LCA(v, u);
    if (lca && !incir[u] && !incir[v]) {
      jump(v);
      jump(u);
    } else {
      if (!incir[v]) v = jump(v);
      if (!incir[u]) u = jump(u);
      if (u == v) {
        int ans = t.sum[1] + min(loop.sum[1], (int)(cir.size()) - 1);
        printf("%d\n", n - ans);
        continue;
      }
      int pre = (cirid[v] - 1 + cir.size()) % cir.size(),
          dp = (cirid[v] - cirid[u] + cir.size()) % cir.size();
      int nxt = (cirid[v] + 1) % cir.size(),
          dn = (cirid[u] - cirid[v] + cir.size()) % cir.size();
      if (dp < dn || (dp == dn && (cir[pre] < cir[nxt]))) {
        if (cirid[v] < cirid[u]) {
          if (cirid[v] > 0) loop.upd(0, cir.size(), 1, 0, cirid[v] - 1);
          loop.upd(0, cir.size(), 1, cirid[u], (int)(cir.size()) - 1);
        } else
          loop.upd(0, cir.size(), 1, cirid[u], cirid[v] - 1);
      } else {
        if (cirid[v] > cirid[u]) {
          loop.upd(0, cir.size(), 1, cirid[v], (int)(cir.size()) - 1);
          if (cirid[u] > 0) loop.upd(0, cir.size(), 1, 0, cirid[u] - 1);
        } else
          loop.upd(0, cir.size(), 1, cirid[v], cirid[u] - 1);
      }
    }
    int ans = t.sum[1] + min(loop.sum[1], (int)(cir.size()) - 1);
    printf("%d\n", n - ans);
  }
  return 0;
}
