#include <bits/stdc++.h>
using namespace std;
int pct(int x) { return __builtin_popcount(x); }
int pct(long long x) { return __builtin_popcountll(x); }
int bit(int x) { return 31 - __builtin_clz(x); }
int bit(long long x) { return 63 - __builtin_clzll(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
long long cdiv(long long a, long long b) {
  return a / b + !(a < 0 || a % b == 0);
}
int nxt_C(int x) {
  int c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
long long nxt_C(long long x) {
  long long c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
vector<int> get_bits(int mask) {
  vector<int> bb;
  while (mask) {
    int b = bit(mask);
    bb.push_back(b);
    mask ^= (1 << b);
  }
  reverse(bb.begin(), bb.end());
  return bb;
}
int get_mask(vector<int> v) {
  int mask = 0;
  for (int x : v) {
    mask ^= (1 << x);
  }
  return mask;
}
template <typename T>
void leftShift(vector<T> &v, long long k) {
  k %= (int)v.size();
  if (k < 0) k += (int)v.size();
  rotate(v.begin(), v.begin() + k, v.end());
}
template <typename T>
void rightShift(vector<T> &v, long long k) {
  leftShift(v, (int)v.size() - k);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
void pr() {}
void sc() {}
template <typename Head, typename... Tail>
void pr(Head H, Tail... T) {
  cout << H << " ";
  pr(T...);
}
template <typename Head, typename... Tail>
void sc(Head &H, Tail &...T) {
  cin >> H;
  sc(T...);
}
string to_string(__int128 x) {
  string s = "";
  bool neg = 0;
  if (x < 0) {
    s += "-";
    neg = 1;
    x = -x;
  }
  if (!x) s += '0';
  while (x) {
    int rem = x % 10;
    s += to_string(rem);
    x /= 10;
  }
  reverse(s.begin() + neg, s.end());
  return s;
}
const int mod = 1e9 + 7;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
template <typename T, typename Z>
class Segtree_With_Lazy {
  struct node {
    T val;
    Z lzy;
  };
  int n;
  vector<node> tr;
  T Id;
  Z Id1;
  inline T op(T a, T b) { return a + b; }
  inline Z op1(Z a, Z b) { return a ^ b; }
  inline node merge(node a, node b) {
    node ans;
    ans.val = op(a.val, b.val);
    ans.lzy = Id1;
    return ans;
  }
  void push_down(int nd, int s, int e) {
    if (tr[nd].lzy == Id1) return;
    tr[nd].val = e - s + 1 - tr[nd].val;
    if (s != e) {
      tr[nd << 1].lzy = op1(tr[nd << 1].lzy, tr[nd].lzy);
      tr[nd << 1 | 1].lzy = op1(tr[nd << 1 | 1].lzy, tr[nd].lzy);
    }
    tr[nd].lzy = Id1;
  }
  void upd(int l, int r, Z x, int nd, int s, int e) {
    push_down(nd, s, e);
    if (s > r || e < l) return;
    if (l <= s && e <= r) {
      tr[nd].lzy = x;
      push_down(nd, s, e);
      return;
    }
    int m = (s + e) >> 1;
    upd(l, r, x, nd << 1, s, m);
    upd(l, r, x, nd << 1 | 1, m + 1, e);
    tr[nd] = merge(tr[nd << 1], tr[nd << 1 | 1]);
  }
  T query(int l, int r, int nd, int s, int e) {
    if (s > r || e < l) return Id;
    push_down(nd, s, e);
    if (l <= s && e <= r) return tr[nd].val;
    int m = (s + e) >> 1;
    return op(query(l, r, nd << 1, s, m), query(l, r, nd << 1 | 1, m + 1, e));
  }

 public:
  Segtree_With_Lazy(int nn) : n(nn), Id(0), Id1(0), tr(4 * nn, {0, 0}) {}
  void upd(int l, int r, Z x) {
    if (l > r) return;
    assert(1 <= l && r <= n);
    upd(l, r, x, 1, 1, n);
  }
  T query(int l, int r) {
    if (l > r) return Id;
    assert(1 <= l && r <= n);
    return query(l, r, 1, 1, n);
  }
};
class Suffix_Array {
  void make_lcp(int const *s) {
    for (int i = 0, k = 0; i < n; ++i)
      if (inv[i] != 0) {
        for (int j = sa[inv[i] - 1]; k < n - max(i, j) && s[i + k] == s[j + k];
             ++k)
          ;
        lcp[inv[i] - 1] = k;
        if (k) --k;
      } else
        k = 0;
  }
  bool cmp(vector<int> const &rank, int i, int j, int l) {
    return i < n - l && j < n - l && rank[i] == rank[j] &&
           rank[i + l] == rank[j + l];
  }
  void build_SA(int const *s) {
    int m = max(256, n);
    sa.resize(n);
    vector<int> x(n), y(n), buck(m);
    int i, j, p;
    for (i = 0; i < n; ++i) buck[x[i] = s[i]]++;
    for (i = 1; i < m; ++i) buck[i] += buck[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--buck[x[i]]] = i;
    for (p = 0, j = 1; p + 1 < n; m = p + 1, j *= 2) {
      for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
      for (i = 0; i < n; ++i)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      memset(buck.data(), 0, sizeof(int) * (m));
      for (i = 0; i < n; ++i) ++buck[x[y[i]]];
      for (i = 1; i < m; ++i) buck[i] += buck[i - 1];
      for (i = n - 1; i >= 0; --i) sa[--buck[x[y[i]]]] = y[i];
      x.swap(y);
      for (p = 0, x[sa[0]] = 0, i = 1; i < n; i++)
        x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p : ++p;
    }
    x.swap(inv);
    y.swap(lcp);
    for (int i = 0; i < n; ++i) inv[sa[i]] = i;
    make_lcp(s);
  }

 public:
  Suffix_Array(int const *s, int _N) : n(_N) { build_SA(s); }
  Suffix_Array(vector<int> const &s) : Suffix_Array(s.data(), s.size()) {}
  Suffix_Array(char const *s, int _N) : n(_N) {
    build_SA(vector<int>(s, s + n).data());
  }
  Suffix_Array(string const &s) : Suffix_Array(s.data(), s.size()) {}
  vector<int> sa, inv, lcp;
  const int n;
};
const int N = 1e5 + 5;
vector<int> g[N];
int depth[N];
int cyc[N];
bool mark[N];
bool vis[N];
int par[N];
int tot;
int T[N], tt;
int part[N];
int sz[N];
int chain_head[N];
void dfs(int u, int p) {
  par[u] = p;
  depth[u] = depth[p] + 1;
  vis[u] = 1;
  for (int v : g[u]) {
    if (!vis[v]) {
      dfs(v, u);
    } else {
      if (v != p && depth[v] < depth[u]) {
        tot = 0;
        int uu = u;
        while (uu != v) {
          cyc[++tot] = uu;
          uu = par[uu];
        }
        cyc[++tot] = uu;
      }
    }
  }
}
void dfs1(int u, int p) {
  sz[u] = 1;
  par[u] = p;
  for (int v : g[u]) {
    if (!mark[v] && v != p) {
      part[v] = part[u];
      dfs1(v, u);
      sz[u] += sz[v];
    }
  }
}
void dfs2(int u, int p) {
  T[u] = ++tt;
  int hc = -1, S = -1;
  for (int v : g[u]) {
    if (!mark[v] && v != p) {
      if (S < sz[v]) {
        S = sz[v], hc = v;
      }
    }
  }
  if (hc != -1) {
    chain_head[hc] = chain_head[u];
    dfs2(hc, u);
  }
  for (int v : g[u]) {
    if (v != hc && !mark[v] && v != p) {
      chain_head[v] = v;
      dfs2(v, u);
    }
  }
}
void solve() {
  int n, m;
  sc(n, m);
  for (int i = 1; i <= n; i++) {
    int u, v;
    sc(u, v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  vector<int> cyc_st, comp;
  for (int i = 1; i <= tot; i++) {
    comp.push_back(cyc[i]);
  }
  sort(comp.begin(), comp.end());
  comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
  for (int i = 1; i <= tot; i++) {
    cyc_st.push_back(lower_bound(comp.begin(), comp.end(), cyc[i]) -
                     comp.begin());
    mark[cyc[i]] = 1;
  }
  for (int i = 1; i <= tot; i++) {
    cyc_st.push_back(lower_bound(comp.begin(), comp.end(), cyc[i]) -
                     comp.begin());
  }
  for (int i = tot; i >= 1; i--) {
    cyc_st.push_back(lower_bound(comp.begin(), comp.end(), cyc[i]) -
                     comp.begin());
  }
  for (int i = tot; i >= 1; i--) {
    cyc_st.push_back(lower_bound(comp.begin(), comp.end(), cyc[i]) -
                     comp.begin());
  }
  for (int i = 1; i <= tot; i++) {
    part[cyc[i]] = i;
    par[cyc[i]] = 0;
    chain_head[cyc[i]] = cyc[i];
    dfs1(cyc[i], 0);
    dfs2(cyc[i], 0);
  }
  Segtree_With_Lazy<int, bool> tree(tt), cycle(tot);
  Suffix_Array SA(cyc_st);
  vector<int> temp(cyc + 1, cyc + tot + 1);
  42;
  for (int i = 1; i <= m; i++) {
    int u, v;
    sc(u, v);
    int t = u;
    while (t) {
      int l = T[chain_head[t]] + (chain_head[t] == cyc[part[t]]), r = T[t];
      42;
      tree.upd(l, r, 1);
      t = par[chain_head[t]];
    }
    t = v;
    while (t) {
      int l = T[chain_head[t]] + (chain_head[t] == cyc[part[t]]), r = T[t];
      tree.upd(l, r, 1);
      t = par[chain_head[t]];
    }
    u = part[u], v = part[v];
    if (!(tot & 1) && abs(v - u) == tot / 2) {
      if (SA.inv[u - 1] > SA.inv[3 * tot - u]) swap(u, v);
    } else {
      if (u > v) swap(u, v);
      if (v - u > tot / 2) {
        swap(u, v);
      }
    }
    42;
    if (u <= v) {
      cycle.upd(u, v - 1, 1);
    } else {
      cycle.upd(v, tot, 1);
      cycle.upd(1, u - 1, 1);
    }
    int v1 = tree.query(1, tt), v2 = cycle.query(1, tot);
    42;
    if (v2 == tot) v2--;
    cout << n - v1 - v2 << '\n';
  }
}
signed main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}
