#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T qmin(const T a, const T b) {
  return a < b ? a : b;
}
template <typename T>
inline T qmax(const T a, const T b) {
  return a > b ? a : b;
}
template <typename T>
inline void getmin(T &a, const T b) {
  if (a > b) a = b;
}
template <typename T>
inline void getmax(T &a, const T b) {
  if (a < b) a = b;
}
inline void fileio(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
const int inf = 1e9 + 7;
const long long linf = 1e17 + 7;
const int N = 1e5 + 7, Node = N << 2, M = N << 1;
int ans;
int lch[Node], rch[Node], val[Node], ul[Node], ur[Node], node;
bool rev[Node];
inline int init(int l, int r) {
  if (l > r) return 0;
  int u = ++node;
  ul[u] = l, ur[u] = r;
  if (l != r) {
    int mid = l + r >> 1;
    lch[u] = init(l, mid);
    rch[u] = init(mid + 1, r);
  }
  return u;
}
inline void settag(int u) {
  val[u] = ur[u] - ul[u] + 1 - val[u];
  rev[u] ^= 1;
}
inline void psd(int u) {
  if (!rev[u]) return;
  rev[u] = 0;
  settag(lch[u]);
  settag(rch[u]);
}
inline void change(int u, int l, int r) {
  if (l > r) return;
  if (l <= ul[u] && ur[u] <= r) {
    settag(u);
  } else {
    psd(u);
    int mid = ul[u] + ur[u] >> 1;
    if (l <= mid) change(lch[u], l, r);
    if (r > mid) change(rch[u], l, r);
    val[u] = val[lch[u]] + val[rch[u]];
  }
}
int v[M], nxt[M];
int head[N], fa[N];
inline void addedge(int p, int x, int y) {
  v[p] = y, nxt[p] = head[x], head[x] = p;
}
inline int find(int x) { return !fa[x] ? x : fa[x] = find(fa[x]); }
int par[N], top[N], id[N], dep[N], root[N];
int child[N], sz[N];
bool isroot[N], on[N];
int rootid[N], pos[N], rootcnt, cyc;
inline void dfs1(int u) {
  sz[u] = 1, child[u] = 0;
  for (int e = head[u]; e; e = nxt[e]) {
    int to = v[e];
    if (isroot[to] || to == par[u]) continue;
    par[to] = u, dep[to] = dep[u] + 1;
    dfs1(to);
    sz[u] += sz[to];
    if (sz[child[u]] < sz[to]) child[u] = to;
  }
}
inline void dfs2(int u, int from) {
  top[u] = from;
  id[u] = (u == from ? 0 : id[par[u]] + 1);
  if (child[u])
    dfs2(child[u], from);
  else
    root[from] = init(1, id[u]);
  for (int e = head[u]; e; e = nxt[e]) {
    int to = v[e];
    if (isroot[to] || to == par[u] || to == child[u]) continue;
    dfs2(to, to);
  }
}
inline int findroot(int x) {
  if (isroot[top[x]]) return top[x];
  return findroot(par[top[x]]);
}
inline pair<int, int> lca(int x, int y) {
  int rx = findroot(x), ry = findroot(y);
  if (rx != ry) return make_pair(rx, ry);
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]])
      x = par[top[x]];
    else
      y = par[top[y]];
  }
  return dep[x] < dep[y] ? make_pair(x, x) : make_pair(y, y);
}
inline void query(int x, int y) {
  if (x == y) return;
  int rt = root[top[x]];
  ans -= val[rt];
  if (top[x] == top[y]) {
    change(rt, id[y] + 1, id[x]);
  } else {
    change(rt, 1, id[x]);
    if (on[top[x]] ^= 1)
      ++ans;
    else
      --ans;
    query(par[top[x]], y);
  }
  ans += val[rt];
}
int n, q;
inline bool findroot(int u, int from, int p) {
  for (int e = head[u]; e; e = nxt[e]) {
    if (v[e] == p) continue;
    if (v[e] == from || findroot(v[e], from, u)) {
      isroot[u] = true;
      rootid[u] = ++rootcnt;
      pos[rootcnt] = u;
      return true;
    }
  }
  return false;
}
inline bool cmp(int x, int y) {
  int len1 = (y + rootcnt - x) % rootcnt, len2 = (x + rootcnt - y) % rootcnt;
  if (len1 != len2) return len1 < len2;
  return pos[x == rootcnt ? 1 : x + 1] < pos[x == 1 ? rootcnt : x - 1];
}
inline void mov(int x, int y) {
  if (x < y) {
    change(cyc, x, y - 1);
  } else {
    change(cyc, x, rootcnt);
    change(cyc, 1, y - 1);
  }
}
int main() {
  scanf("%d%d", &n, &q);
  int any = 0;
  for (int i = 1; i <= n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    addedge(i << 1, x, y);
    addedge(i << 1 ^ 1, y, x);
    int tx = find(x), ty = find(y);
    if (tx == ty)
      any = x;
    else
      fa[tx] = ty;
  }
  findroot(any, any, -1);
  cyc = init(1, rootcnt);
  for (int i = 1; i <= n; ++i) {
    if (!isroot[i]) continue;
    dfs1(i), dfs2(i, i);
  }
  cerr << "end_init" << endl;
  cerr << "----------" << endl;
  for (int i = 1; i <= n; ++i) cerr << par[i] << "->" << i << endl;
  cerr << "rootcnt=" << rootcnt << endl;
  cerr << "cyc_size=" << ur[cyc] - ul[cyc] + 1 << endl;
  for (int i = 1; i <= rootcnt; ++i) cerr << pos[i] << " ";
  cerr << endl;
  cerr << "----------" << endl;
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    pair<int, int> p = lca(x, y);
    query(x, p.first);
    query(y, p.second);
    if (p.first != p.second) {
      ans -= val[cyc];
      int idx = rootid[p.first], idy = rootid[p.second];
      if (cmp(idx, idy)) {
        mov(idx, idy);
      } else {
        mov(idy, idx);
      }
      ans += val[cyc];
    }
    printf("%d\n", n - ans + (val[cyc] == rootcnt));
  }
  return 0;
}
