#include <bits/stdc++.h>
using namespace std;
int t, T, L, mb, mdb, ans, d[100005], z[100005], g[100005], o[100005],
    fa[100005], FA[100005], p[100005 * 2], nxt[100005 * 2];
struct LCtree {
  int g, t, l[100005], r[100005], z[100005], a[100005], x[100005], y[100005],
      fa[100005], root[100005];
  void put(int i, int j) {
    if (i && j) z[i] = !z[i], a[i] = !a[i], swap(x[i], y[i]);
  }
  void lazy(int i) { put(l[i], z[i]), put(r[i], z[i]), z[i] = 0; }
  void rt(int i, int j) {
    if (l[i] == j)
      l[i] = r[j], fa[r[j]] = i, r[j] = i;
    else
      r[i] = l[j], fa[l[j]] = i, l[j] = i;
    root[j] = root[i], root[i] = 0;
    if (l[fa[i]] == i)
      l[fa[i]] = j;
    else if (r[fa[i]] == i)
      r[fa[i]] = j;
    fa[j] = fa[i], fa[i] = j;
    x[i] = x[l[i]] + x[r[i]] + a[i], y[i] = y[l[i]] + y[r[i]] + 1 - a[i];
    ;
    x[j] = x[l[j]] + x[r[j]] + a[j], y[j] = y[l[j]] + y[r[j]] + 1 - a[j];
    ;
  }
  void splay(int i, int j) {
    if (root[i]) lazy(i);
    while (!root[i]) {
      lazy(fa[i]);
      lazy(i);
      rt(fa[i], i);
    };
    if (j) {
      root[g = r[i]] = 1;
      r[i] = 0;
      x[i] = x[l[i]] + x[r[i]] + a[i], y[i] = y[l[i]] + y[r[i]] + 1 - a[i];
      ;
    }
  }
  void access(int i) {
    splay(t = i, 1);
    while (fa[i]) {
      splay(t = fa[i], 1);
      r[t] = 1, rt(t, i);
    };
  }
  void cover(int i) {
    access(i);
    splay(L, 0);
    ans += y[r[L]] - x[r[L]];
    put(r[L], 1);
  }
} TREE;
void link(int a, int b) { nxt[++t] = d[a], d[a] = t, p[t] = b; }
int find(int i) { return (FA[i] == i) ? i : FA[i] = find(FA[i]); }
void dfs(int i, int h) {
  z[++t] = i, o[i] = t;
  for (int k = d[i], j = p[k]; k; k = nxt[k], j = p[k])
    if ((h ^ k) != 1) {
      if (o[j]) {
        mb = k;
        for (int I = o[j]; I <= t; I++) g[++T] = z[I];
      } else
        dfs(j, k);
    };
  t--;
}
void dfs2(int i, int h) {
  for (int k = d[i], j = p[k]; k; k = nxt[k], j = p[k])
    if ((h ^ k) != 1 && ((k ^ mb) > 1)) {
      fa[j] = i;
      dfs2(j, k);
    };
}
int main() {
  int n, m, a, b, mdb = 0;
  t = 1;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a, &b);
    link(a, b);
    link(b, a);
  };
  t = 0;
  dfs(1, 0);
  dfs2(g[1], 0);
  for (int i = 0; i < 100005; i++) o[i] = 0;
  for (int i = 1; i <= T; i++) o[g[i]] = i;
  for (int i = 1; i <= n; i++) FA[i] = (o[i]) ? i : fa[i];
  for (int i = 1; i <= n; i++) find(i);
  for (int i = 1; i <= n; i++) {
    TREE.fa[i] = fa[i];
    TREE.y[i] = TREE.root[i] = 1;
  };
  g[0] = g[T], L = g[T + 1] = g[1];
  while (m--) {
    scanf("%d%d", &a, &b);
    int Fa = FA[a], Fb = FA[b];
    int d1 = abs(o[Fa] - o[Fb]);
    int g1, g2;
    if (o[Fa] < o[Fb])
      g1 = g[o[Fa] + 1], g2 = g[o[Fa] - 1];
    else
      g1 = g[o[Fa] - 1], g2 = g[o[Fa] + 1];
    TREE.cover(a);
    TREE.cover(b);
    if (d1 > T - d1 || ((d1 == T - d1) && g1 > g2)) {
      mdb = !mdb;
      if (mdb)
        ans++;
      else
        ans--;
      TREE.cover(g[T]);
    };
    TREE.access(g[T]);
    int al = TREE.x[g[T]] + mdb == T;
    printf("%d\n", n - ans + al);
  };
  return 0;
}
