#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, LG = 17;
int N, Q, ret = 0;
vector<int> adj[100001], CM;
int H[100001], P[100001], jump[100001][LG];
int id[100001], sz[100001], par[100001], root = 0;
struct Segtree {
  int n;
  vector<int> seg;
  vector<bool> lz;
  inline void init(int N) {
    n = N;
    seg.assign(4 * N, 0);
    lz.assign(4 * N, 0);
  }
  inline void prop(int idx, int L, int R) {
    if (L <= R && lz[idx]) {
      seg[idx] = (R - L + 1) - seg[idx];
      if (L < R) {
        lz[2 * idx] = !lz[2 * idx];
        lz[2 * idx + 1] = !lz[2 * idx + 1];
      }
      lz[idx] = 0;
    }
  }
  void upd(int idx, int L, int R, int l, int r) {
    l = max(L, l);
    r = min(R, r);
    prop(idx, L, R);
    if (l <= r) {
      if (L == l && R == r) {
        lz[idx] = !lz[idx];
        prop(idx, L, R);
      } else {
        int M = L + R >> 1;
        upd(2 * idx, L, M, l, r);
        upd(2 * idx + 1, M + 1, R, l, r);
        seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
      }
    }
  }
  inline void update(int l, int r, bool b) {
    if (b) swap(l, r);
    if (l > r) {
      upd(1, 0, n - 1, l, n - 1);
      upd(1, 0, n - 1, 0, r - 1);
    } else {
      upd(1, 0, n - 1, l, r - 1);
    }
  }
  inline int sum() { return seg[1]; }
};
Segtree cycle;
vector<Segtree> chain;
void init() {
  for (int i = 0; i < N; i++) {
    H[i] = -1;
  }
  H[root] = 0;
}
int DFS1(int u, int p) {
  int ret = INF;
  for (const int &v : adj[u]) {
    if (v != p) {
      if (H[v] == -1) {
        H[v] = H[u] + 1;
        ret = DFS1(v, u);
        if (ret < INF) break;
      }
      if (H[u] > H[v]) {
        ret = H[v];
        break;
      }
    }
  }
  if (H[u] >= ret) {
    P[u] = CM.size();
    id[u] = -1;
    CM.push_back(u);
    root = u;
  }
  return ret;
}
void DFS2(int u, int p) {
  jump[u][0] = p;
  for (int i = 1; i < LG; i++) {
    if (jump[u][i - 1] == -1)
      jump[u][i] = -1;
    else
      jump[u][i] = jump[jump[u][i - 1]][i - 1];
  }
  sz[u] = 1;
  for (const int &v : adj[u]) {
    if (v != p && id[v] != -1) {
      H[v] = H[u] + 1;
      DFS2(v, u);
      sz[u] += sz[v];
    }
  }
}
void DFS3(int u, int p) {
  int hvy = -1;
  for (const int &v : adj[u]) {
    if (v != p && (hvy == -1 || sz[v] > sz[hvy])) hvy = v;
  }
  if (hvy != -1) {
    P[hvy] = P[u] + 1;
    id[hvy] = id[u];
    par[hvy] = par[u];
    DFS3(hvy, u);
  } else {
    chain[id[u]].init(P[u] + 1);
  }
  for (const int &v : adj[u]) {
    if (v != p && v != hvy) {
      P[v] = 0;
      id[v] = chain.size();
      par[v] = u;
      chain.push_back(Segtree());
      DFS3(v, u);
    }
  }
}
inline void rebuild() {
  vector<pair<int, int> > keep;
  vector<int> k2;
  for (int i = 0; i < N; i++) H[i] = -1;
  for (int i = 0; i < CM.size(); i++) {
    int u = CM[i], l = CM[(i + CM.size() - 1) % CM.size()],
        r = CM[(i + 1) % CM.size()];
    for (const int &v : adj[u]) {
      if (v != l && v != r) {
        keep.push_back({v, u});
        k2.push_back(v);
      }
    }
    adj[u].clear();
  }
  for (const int &u : k2) adj[root].push_back(u);
  cycle.init(CM.size());
  H[root] = 0;
  DFS2(root, -1);
  for (const pair<int, int> &u : keep) {
    chain.push_back(Segtree());
    P[u.first] = 0;
    id[u.first] = chain.size() - 1;
    par[u.first] = u.second;
    DFS3(u.first, u.second);
  }
}
inline int LCA(int u, int v) {
  if (H[u] > H[v]) swap(u, v);
  for (int i = LG - 1; H[v] - H[u]; i--) {
    if ((H[v] - H[u]) >= (1 << i)) {
      v = jump[v][i];
    }
  }
  if (u == v) return u;
  for (int i = LG - 1; i >= 0; i--) {
    if (jump[u][i] != jump[v][i]) {
      u = jump[u][i];
      v = jump[v][i];
    }
  }
  return jump[v][0];
}
inline int solveChain(int u, int d) {
  if (id[u] == -1) return u;
  while (d) {
    if (P[u] + 1 <= d) {
      ret += chain[id[u]].sum();
      chain[id[u]].update(0, P[u] + 1, 0);
      ret -= chain[id[u]].sum();
      d -= P[u] + 1;
      u = par[u];
    } else {
      ret += chain[id[u]].sum();
      chain[id[u]].update(P[u] + 1 - d, P[u] + 1, 0);
      ret -= chain[id[u]].sum();
      return -1;
    }
  }
  if (id[u] != -1) return -1;
  return u;
}
inline int getDist(int u, int v, bool b) {
  if (b)
    return (P[u] - P[v] + CM.size()) % CM.size();
  else
    return (P[v] - P[u] + CM.size()) % CM.size();
}
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  ret = N;
  for (int i = 0; i < N; i++) {
    int u, v;
    cin >> u >> v;
    adj[u - 1].push_back(v - 1);
    adj[v - 1].push_back(u - 1);
  }
  init();
  DFS1(0, -1);
  rebuild();
  for (int i = 0; i < Q; i++) {
    int u, v, ut, vt, L;
    cin >> u >> v;
    u--;
    v--;
    ut = (id[u] == -1) ? root : u;
    vt = (id[v] == -1) ? root : v;
    L = LCA(ut, vt);
    ut = H[ut] - H[L];
    vt = H[vt] - H[L];
    u = solveChain(u, ut);
    v = solveChain(v, vt);
    if (u >= 0) {
      int l = CM[(P[u] + 1) % CM.size()],
          r = CM[(P[u] + CM.size() - 1) % CM.size()];
      ret += min(cycle.n - 1, cycle.sum());
      if (make_pair(getDist(u, v, 0), l) < make_pair(getDist(u, v, 1), r))
        cycle.update(P[u], P[v], 0);
      else
        cycle.update(P[u], P[v], 1);
      ret -= min(cycle.n - 1, cycle.sum());
    }
    cout << ret << "\n";
  }
  return 0;
}
