#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int N = 2e5 + 100, T = 1100, OO = 150, M = 1e9 + 7, P = 6151, SQ = 360,
          lg = 18;
vector<int> v[N], g[N], cyc;
int pr[N], lc[N][lg + 5], nw[N], h[N], sz[N], st[N], be[N], en[N], mark[N], n,
    m, nxt = 0;
bool cmp(int x, int y) { return sz[x] > sz[y]; }
bool is;
bool Cycle(int x) {
  for (auto u : v[x]) {
    if (u == pr[x]) continue;
    if (pr[u] == -1) {
      pr[u] = x;
      if (Cycle(u)) return true;
      continue;
    }
    while (x != pr[u]) cyc.push_back(x), x = pr[x];
    return true;
  }
  return false;
}
void dfssz(int x) {
  sz[x] = 1;
  lc[x][0] = (pr[x] == -1 ? 0 : pr[x]);
  for (int i = 1; i <= lg; i++) lc[x][i] = lc[lc[x][i - 1]][i - 1];
  for (auto u : v[x])
    if (pr[u] == -1)
      g[x].push_back(u), h[u] = h[x] + 1, pr[u] = x, dfssz(u), sz[x] += sz[u];
}
void dfs(int x) {
  if (mark[x]) nw[x] = x;
  st[x] = nxt++;
  if (pr[x] != -1 && st[pr[x]] == st[x] - 1)
    be[x] = be[pr[x]];
  else
    be[x] = x;
  sort(g[x].begin(), g[x].end(), cmp);
  for (auto u : g[x]) nw[u] = nw[x], dfs(u);
  if ((int)g[x].size())
    en[x] = en[g[x][0]];
  else
    en[x] = x;
}
int Lca(int x, int y) {
  if (h[x] < h[y]) swap(x, y);
  for (int i = lg; i >= 0; i--)
    if (h[x] - (1 << i) >= h[y]) x = lc[x][i];
  if (x == y) return x;
  for (int i = lg; i >= 0; i--)
    if (lc[x][i] != lc[y][i]) x = lc[x][i], y = lc[y][i];
  return lc[x][0];
}
struct node {
  int od, ev;
  bool lz;
} seg[N << 2];
void build(int c, int b, int e) {
  if (e - b == 1) {
    seg[c] = {0, 1, false};
    return;
  }
  int mid = (b + e) >> 1;
  build(c << 1, b, mid), build(c << 1 | 1, mid, e);
  seg[c] = {0, e - b, false};
}
void shift(int c) {
  if (seg[c].lz == false) return;
  seg[c << 1].lz ^= 1, seg[c << 1 | 1].lz ^= 1;
  swap(seg[c << 1].od, seg[c << 1].ev);
  swap(seg[c << 1 | 1].od, seg[c << 1 | 1].ev);
  seg[c].lz = false;
}
void upd(int c, int b, int e, int l, int r) {
  if (r <= b || e <= l) return;
  if (l <= b && e <= r) {
    swap(seg[c].od, seg[c].ev);
    seg[c].lz ^= 1;
    return;
  }
  int mid = (b + e) >> 1;
  shift(c);
  upd(c << 1, b, mid, l, r), upd(c << 1 | 1, mid, e, l, r);
  seg[c].ev = seg[c << 1].ev + seg[c << 1 | 1].ev;
  seg[c].od = seg[c << 1].od + seg[c << 1 | 1].od;
}
void change(int x, int y) {
  if (h[x] < h[y]) swap(x, y);
  while (h[x] > h[y]) {
    if (h[be[x]] <= h[y]) {
      upd(1, 0, n, st[g[y][0]], st[x] + 1);
      return;
    }
    upd(1, 0, n, st[be[x]], st[x] + 1);
    x = pr[be[x]];
  }
}
void get(int x, int y) {
  int z = x;
  if (h[x] < h[y]) swap(x, y);
  int t = (int)cyc.size();
  if (t % 2 == 1)
    t++;
  else if (abs(mark[x] - mark[y]) == t / 2) {
    if (x == z) {
      if (cyc[mark[z] % t] > cyc[(mark[z] - 2 + t) % t]) {
        change(x, y);
      } else {
        change(x, cyc.back()), change(y, cyc[0]);
        is ^= 1;
      }
    } else {
      if (cyc[mark[z] % t] < cyc[(mark[z] - 2 + t) % t]) {
        change(x, y);
      } else {
        change(x, cyc.back()), change(y, cyc[0]);
        is ^= 1;
      }
    }
    return;
  }
  if (abs(mark[x] - mark[y]) < t / 2) {
    change(x, y);
    return;
  } else {
    change(x, cyc.back()), change(cyc[0], y);
    is ^= 1;
  }
}
bool check() {
  if (!is) return false;
  int cnt = seg[1].od;
  change(cyc[0], cyc.back());
  cnt -= seg[1].od;
  change(cyc[0], cyc.back());
  if (cnt != (int)cyc.size() - 1) return true;
  return false;
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  memset(pr, -1, sizeof(pr));
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  pr[1] = 0;
  Cycle(1);
  reverse(cyc.begin(), cyc.end());
  int ct = 1;
  for (auto u : cyc) mark[u] = ct++;
  memset(pr, -1, sizeof(pr));
  pr[cyc[0]] = 0;
  dfssz(cyc[0]);
  dfs(cyc[0]);
  n = nxt;
  if (cyc[0] != pr[cyc[1]]) assert(0);
  build(1, 0, n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    int z = Lca(x, y);
    if (h[nw[x]] < h[z]) {
      change(x, z);
      change(y, z);
      cout << n - (seg[1].od + check()) << endl;
      continue;
    }
    if (nw[x] != z && nw[y] != z) assert(0);
    change(x, nw[x]);
    change(y, nw[y]);
    get(nw[x], nw[y]);
    cout << n - (seg[1].od + check()) << endl;
  }
  return 0;
}
