#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> G[200006];
int vs[200006];
vector<int> cir;
int oc[200006];
bool cfs(int u, int f) {
  vs[u] = 1;
  for (int v : G[u])
    if (v != f) {
      if (vs[v]) {
        cir.push_back(u);
        oc[u] = oc[v] = 1;
        return true;
      }
      int fg = cfs(v, u);
      if (fg) {
        cir.push_back(u);
        if (oc[u]) return false;
        oc[u] = 1;
        return true;
      }
    }
  return false;
}
int rt[200006];
int fa[200006], dep[200006], top[200006], hea[200006], siz[200006], dfn[200006],
    R[200006], clo;
void dfs(int u, int f, int s) {
  rt[u] = s;
  dep[u] = dep[f] + 1, fa[u] = f;
  siz[u] = 1;
  for (int v : G[u])
    if (!oc[v] && v != f) {
      dfs(v, u, s);
      siz[u] += siz[v];
      if (!hea[u] || siz[v] > siz[hea[u]]) hea[u] = v;
    }
}
void dfs$(int u, int to) {
  dfn[u] = ++clo;
  top[u] = to;
  if (hea[u]) dfs$(hea[u], to);
  for (int v : G[u])
    if (!oc[v] && v != fa[u] && v != hea[u]) dfs$(v, v);
  R[u] = clo;
}
struct sgt {
  int T[200006 << 2], lz[200006 << 2];
  inline void rev(int x, int l) { lz[x] ^= 1, T[x] = l - T[x]; }
  void pd(int x, int l) {
    if (lz[x]) {
      rev(x << 1, l - (l >> 1));
      rev(x << 1 | 1, l >> 1);
      lz[x] = 0;
    }
  }
  void pu(int rt) { T[rt] = T[rt << 1] + T[rt << 1 | 1]; }
  void mdf(int rt, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
      rev(rt, r - l + 1);
      return;
    }
    pd(rt, r - l + 1);
    int m = l + r >> 1;
    if (L <= m) mdf(rt << 1, l, m, L, R);
    if (R > m) mdf(rt << 1 | 1, m + 1, r, L, R);
    pu(rt);
  }
  int que(int rt, int l, int r, int L, int R) {
    if (L <= l && R >= r) return T[rt];
    pd(rt, r - l + 1);
    int m = l + r >> 1, as = 0;
    if (L <= m) as += que(rt << 1, l, m, L, R);
    if (R > m) as += que(rt << 1 | 1, m + 1, r, L, R);
    return as;
  }
} T, C;
int te = 0;
void wkr(int u, int v) {
  te -= T.T[1];
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    T.mdf(1, 1, n, dfn[top[u]], dfn[u]);
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) swap(u, v);
  if (u != v) T.mdf(1, 1, n, dfn[v] + 1, dfn[u]);
  te += T.T[1];
}
int bc[200006];
void solve() {
  cin >> n >> m;
  for (int i = (1), iend = (n); i <= iend; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v), G[v].push_back(u);
  }
  cir.push_back(0);
  cfs(1, 1);
  int sc = cir.size() - 1;
  for (int i = (1), iend = (n); i <= iend; ++i)
    if (oc[i]) {
      dfs(i, i, i);
      dfs$(i, i);
    }
  for (int i = (1), iend = (sc); i <= iend; ++i) {
    bc[cir[i]] = i;
  }
  cir.push_back(cir[1]), cir[0] = cir[sc];
  for (int i = (1), iend = (m); i <= iend; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    if (rt[u] == rt[v]) {
      wkr(u, v);
    } else {
      wkr(u, rt[u]), wkr(v, rt[v]);
      te -= C.T[1] == sc ? C.T[1] - 1 : C.T[1];
      int tu = bc[rt[u]], tv = bc[rt[v]];
      if (tv > tu &&
          (tv - tu < (sc + 1) / 2 ||
           ((~sc & 1) && tv - tu == sc / 2 && cir[tu + 1] < cir[tu - 1]))) {
        C.mdf(1, 1, sc, tu, tv - 1);
      } else if (tv > tu) {
        if (tu != 1) C.mdf(1, 1, sc, 1, tu - 1);
        C.mdf(1, 1, sc, tv, n);
      } else if (tu - tv < (sc + 1 >> 1) || ((~sc & 1) && tu - tv == sc / 2 &&
                                             cir[tu - 1] < cir[tu + 1])) {
        C.mdf(1, 1, sc, tv, tu - 1);
      } else {
        if (tv != 1) C.mdf(1, 1, sc, 1, tv - 1);
        C.mdf(1, 1, sc, tu, n);
      }
      te += C.T[1] == sc ? C.T[1] - 1 : C.T[1];
    }
    printf("%d\n", n - te);
  }
}
signed main() { solve(); }
