#include <bits/stdc++.h>
using std::swap;
const int maxn = 100000 + 10;
const int maxlogn = 17 + 1;
int n, m, group;
int e_tot, e_l[maxn], e_t[maxn << 1], e_next[maxn << 1], e_x[maxn];
int papa[maxn][maxlogn];
int loop_size, loop[maxn];
bool in_loop[maxn], vis[maxn];
int head, tail, queue[maxn];
int size[maxn], up[maxn];
int tree_belong[maxn], tree_dep[maxn], segment_belong[maxn], segment_dep[maxn],
    segment_bottom[maxn], segment_size[maxn];
int top, stack[maxn];
int ans;
class Segment {
  int L, R;
  bool flag;
  Segment *lc, *rc;

 public:
  int cnt;
  void build(int l, int r) {
    L = l, R = r, flag = false, cnt = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    lc = new Segment;
    lc->build(l, mid);
    rc = new Segment;
    rc->build(mid + 1, r);
  }
  void turn(int l, int r) {
    assert(l <= r);
    ans -= cnt;
    turn(l, r, false);
    ans += cnt;
  }
  void turn(int l, int r, bool f) {
    if (f) {
      flag = !flag;
      cnt = R - L + 1 - cnt;
      f = false;
    }
    if (l > R || r < L) return;
    if (l <= L && R <= r) {
      flag = !flag;
      cnt = R - L + 1 - cnt;
      return;
    }
    if (flag) {
      flag = false;
      f = true;
    }
    lc->turn(l, r, f);
    rc->turn(l, r, f);
    cnt = lc->cnt + rc->cnt;
  }
} segment[maxn];
inline int go_up(int x, const int &k) {
  for (int i = maxlogn - 1; i >= 0; --i)
    if (k & (1 << i)) x = papa[x][i];
  return x;
}
inline int lca(int x, int y) {
  if (tree_dep[x] < tree_dep[y]) swap(x, y);
  int k = tree_dep[x] - tree_dep[y];
  if ((x = go_up(x, k)) == y) return x;
  for (int i = maxlogn - 1; i >= 0; --i)
    if (papa[x][i] != papa[y][i]) x = papa[x][i], y = papa[y][i];
  assert(papa[x][0] == papa[y][0]);
  return papa[x][0];
}
inline void tree_rush(int x, int y) {
  assert(tree_dep[x] >= tree_dep[y]);
  int gy = segment_belong[y];
  while (x != y) {
    int gx = segment_belong[x];
    if (gx != gy) {
      segment[gx].turn(segment_dep[x], segment_size[gx]);
      x = go_up(
          x, segment_size[gx] - (tree_dep[segment_bottom[gx]] - tree_dep[x]));
    } else {
      segment[gx].turn(segment_dep[x], segment_dep[y] - 1);
      x = y;
    }
  }
}
inline void loop_rush(int x, int y) {
  x = segment_dep[x], y = segment_dep[y];
  assert(x != y);
  int len = y - x;
  if (len < 0) len = -len;
  if (len * 2 < loop_size) {
    if (x > y) swap(x, y);
    segment[0].turn(x, y - 1);
  } else if (len * 2 > loop_size) {
    if (x > y) swap(x, y);
    if (1 <= x - 1) segment[0].turn(1, x - 1);
    segment[0].turn(y, loop_size);
  } else {
    int right = x + 1, left = x - 1;
    if (right > loop_size) right = 1;
    if (left < 1) left = loop_size;
    if (loop[right] > loop[left]) swap(x, y);
    if (x < y)
      segment[0].turn(x, y - 1);
    else {
      if (1 <= y - 1) segment[0].turn(1, y - 1);
      segment[0].turn(x, loop_size);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  e_tot = 0;
  memset(e_l, 0, sizeof(e_l));
  for (int i = 0, a, b; i < n; ++i) {
    scanf("%d%d", &a, &b);
    e_t[++e_tot] = b, e_next[e_tot] = e_l[a], e_l[a] = e_tot;
    e_t[++e_tot] = a, e_next[e_tot] = e_l[b], e_l[b] = e_tot;
  }
  loop_size = 0;
  memset(papa, 0, sizeof(papa));
  memset(vis, 0, sizeof(vis));
  memcpy(e_x, e_l, sizeof(e_l));
  top = 0;
  vis[stack[++top] = 1] = true;
  while (top && loop_size == 0) {
    int x = stack[top], y;
    bool flag = true;
    for (int i = e_x[x]; i > 0; i = e_x[x]) {
      e_x[x] = e_next[i];
      if ((y = e_t[i]) != papa[x][0]) {
        flag = false;
        if (vis[y]) {
          loop[++loop_size] = y;
          do {
            loop[++loop_size] = x;
            x = papa[x][0];
          } while (x != y);
        } else {
          papa[y][0] = x;
          vis[stack[++top] = y] = true;
        }
        break;
      }
    }
    if (flag) --top;
  }
  group = 0;
  memset(segment_dep, 0, sizeof(segment_dep));
  memset(in_loop, 0, sizeof(in_loop));
  for (int i = 1; i <= loop_size; ++i)
    segment_dep[loop[i]] = i, in_loop[loop[i]] = true;
  segment[0].build(1, loop_size);
  memset(papa, 0, sizeof(papa));
  memset(tree_dep, 0, sizeof(tree_dep));
  memset(size, 0, sizeof(size));
  memset(up, 0, sizeof(up));
  for (int i = 1; i <= loop_size; ++i) {
    head = tail = 0;
    queue[++tail] = loop[i];
    while (head != tail) {
      int x = queue[++head], y;
      for (int i = e_l[x]; i > 0; i = e_next[i])
        if ((y = e_t[i]) != papa[x][0] && !in_loop[y]) {
          papa[y][0] = x;
          tree_dep[y] = tree_dep[x] + 1;
          queue[++tail] = y;
        }
    }
    for (int j = 1; j <= tail; ++j) tree_belong[queue[j]] = loop[i];
    for (int i = tail; i > 1; --i) {
      int x = queue[i], y, maxsize = 0, maxind = -1;
      size[x] = 1;
      for (int i = e_l[x]; i > 0; i = e_next[i])
        if ((y = e_t[i]) != papa[x][0] && !in_loop[y]) {
          size[x] += size[y];
          if (size[y] > maxsize) maxsize = size[maxind = y];
        }
      if (maxind != -1) up[maxind] = x;
    }
    for (int i = tail; i > 1; --i)
      if (segment_dep[queue[i]] == 0) {
        ++group;
        int x = queue[i];
        top = 0;
        do {
          stack[++top] = x;
          segment_dep[x] = top;
          segment_belong[x] = group;
          x = up[x];
        } while (x);
        segment_bottom[group] = stack[1];
        segment_size[group] = top;
        segment[group].build(1, top);
      }
  }
  for (int j = 1; j < maxlogn; ++j)
    for (int i = 1; i <= n; ++i) papa[i][j] = papa[papa[i][j - 1]][j - 1];
  ans = n;
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (tree_belong[a] == tree_belong[b]) {
      int c = lca(a, b);
      tree_rush(a, c);
      tree_rush(b, c);
    } else {
      tree_rush(a, tree_belong[a]);
      tree_rush(b, tree_belong[b]);
      loop_rush(tree_belong[a], tree_belong[b]);
    }
    if (segment[0].cnt == 0) ++ans;
    printf("%d\n", ans);
    if (segment[0].cnt == 0) --ans;
  }
  return 0;
}
