#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1073741824")
using namespace std;
const int nmax = 100100;
int countEnabled;
class SegmentTree {
  struct node {
    int val;
    int inverted;
    node() { val = inverted = 0; }
  };
  vector<node> t;
  int n;
  void push(int v, int tl, int tr) {
    if (tl != tr && t[v].inverted) {
      int mid = (tl + tr) / 2;
      t[2 * v].inverted ^= 1;
      t[2 * v].val = (mid + 1 - tl) - t[2 * v].val;
      t[2 * v + 1].inverted ^= 1;
      t[2 * v + 1].val = (tr - mid) - t[2 * v + 1].val;
    }
    t[v].inverted = 0;
  }
  void upd(int v, int tl, int tr, int l, int r) {
    if (tl == l && tr == r) {
      countEnabled -= t[v].val;
      t[v].val = (tr - tl + 1) - t[v].val;
      countEnabled += t[v].val;
      t[v].inverted ^= 1;
    } else {
      push(v, tl, tr);
      int mid = (tl + tr) / 2;
      if (r <= mid) {
        upd(2 * v, tl, mid, l, r);
      } else if (mid < l) {
        upd(2 * v + 1, mid + 1, tr, l, r);
      } else {
        upd(2 * v, tl, mid, l, mid);
        upd(2 * v + 1, mid + 1, tr, mid + 1, r);
      }
      t[v].val = t[2 * v].val + t[2 * v + 1].val;
    }
  }
  int get(int v, int tl, int tr, int l, int r) {
    if (tl == l && tr == r) {
      return t[v].val;
    } else {
      push(v, tl, tr);
      int mid = (tl + tr) / 2;
      if (r <= mid) {
        return get(2 * v, tl, mid, l, r);
      } else if (mid < l) {
        return get(2 * v + 1, mid + 1, tr, l, r);
      } else {
        return get(2 * v, tl, mid, l, mid) +
               get(2 * v + 1, mid + 1, tr, mid + 1, r);
      }
    }
  }

 public:
  SegmentTree(int n_) {
    n = n_;
    t.assign(4 * n + 4, node());
  }
  int get(int l, int r) {
    assert(1 <= l && l <= r && r <= n);
    return get(1, 1, n, l, r);
  }
  void upd(int l, int r) {
    assert(1 <= l && l <= r && r <= n);
    upd(1, 1, n, l, r);
  }
};
bool used[nmax];
int par[nmax][20];
vector<int> g[nmax];
int lev[nmax];
int treeRoot[nmax];
int k[nmax];
int topEdge[nmax];
int p[nmax];
int have[nmax];
int find(int v) {
  if (p[v] == v) return v;
  return p[v] = find(p[v]);
}
void unite(int u, int v) {
  u = find(u);
  v = find(v);
  p[u] = v;
  have[v] += have[u];
}
SegmentTree* sgTrees[nmax];
class TreeDecomposition {
  int root;
  queue<int> q;
  void dfs(int v, int p) {
    k[v] = 1;
    used[v] = true;
    lev[v] = lev[p] + 1;
    par[v][0] = p;
    for (int i = 1; i < 20; ++i) par[v][i] = par[par[v][i - 1]][i - 1];
    treeRoot[v] = treeRoot[p];
    int toMax = -1;
    for (int(i) = 0; (i) < (int((g[v]).size())); ++(i)) {
      int to = g[v][i];
      if (!used[to]) {
        dfs(to, v);
        k[v] += k[to];
        if (toMax == -1 || k[to] > k[toMax]) toMax = to;
      }
    }
    if (toMax != -1 && k[v] < 2 * k[toMax]) unite(toMax, v);
  }
  void dfsDec(int v) {
    if (p[v] == v && have[v] > 1) sgTrees[v] = new SegmentTree(have[v] - 1);
    used[v] = true;
    for (int(i) = 0; (i) < (int((g[v]).size())); ++(i)) {
      int to = g[v][i];
      if (!used[to]) dfsDec(to);
    }
  }

 public:
  void build(int root_) {
    root = root_;
    treeRoot[root] = root;
    dfs(root, root);
  }
  void decomposite() { dfsDec(root); }
  int lca(int v, int u) {
    int d = lev[v] - lev[u];
    if (d < 0) {
      swap(v, u);
      d = -d;
    }
    for (int i = 20; i--;)
      if ((d >> i) & 1) v = par[v][i];
    if (u == v) return v;
    for (int i = 20; i--;)
      if (par[v][i] != par[u][i]) {
        v = par[v][i];
        u = par[u][i];
      }
    return par[u][0];
  }
  void invert(int a, int b) {
    while (find(a) != find(b)) {
      int p = find(b);
      if (p == b) {
        countEnabled -= topEdge[b];
        topEdge[b] ^= 1;
        countEnabled += topEdge[b];
        b = par[b][0];
      } else {
        sgTrees[p]->upd(1, lev[b] - lev[p]);
        b = p;
      }
    }
    if (a != b)
      sgTrees[find(a)]->upd(lev[a] - lev[find(a)] + 1, lev[b] - lev[find(a)]);
  }
};
vector<int> cycle;
int cycleP[nmax];
bool dfs1(int v, int p) {
  cycle.push_back(v);
  used[v] = true;
  for (int(i) = 0; (i) < (int((g[v]).size())); ++(i)) {
    int to = g[v][i];
    if (to == p) continue;
    if (used[to]) {
      cycle.push_back(to);
      return true;
    } else {
      if (dfs1(to, v)) return true;
    }
  }
  cycle.pop_back();
  return false;
}
TreeDecomposition trees[nmax];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int(i) = 0; (i) < (n); ++(i)) {
    int v, u;
    scanf("%d%d", &v, &u);
    --v, --u;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  dfs1(0, -1);
  for (int(i) = 0; (i) < (int((cycle).size())); ++(i)) {
    if (cycle[i] == cycle.back()) {
      assert(i + 1 != cycle.size());
      rotate(cycle.begin(), cycle.begin() + i + 1, cycle.end());
      cycle.resize(cycle.size() - i - 1);
      break;
    }
  }
  memset((cycleP), -1, sizeof(cycleP));
  memset((used), 0, sizeof(used));
  for (int(i) = 0; (i) < (int((cycle).size())); ++(i)) {
    int v = cycle[i];
    cycleP[v] = i;
    treeRoot[v] = v;
    used[v] = true;
  }
  for (int(i) = 0; (i) < (n); ++(i)) have[i] = 1, p[i] = i;
  for (int(i) = 0; (i) < (int((cycle).size())); ++(i))
    trees[cycle[i]].build(cycle[i]);
  memset((used), 0, sizeof(used));
  for (int(i) = 0; (i) < (int((cycle).size())); ++(i)) used[cycle[i]] = true;
  for (int(i) = 0; (i) < (int((cycle).size())); ++(i))
    trees[cycle[i]].decomposite();
  SegmentTree cycleTree(cycle.size());
  for (int(i) = 0; (i) < (m); ++(i)) {
    int v, u;
    scanf("%d%d", &v, &u);
    --v, --u;
    if (treeRoot[v] == treeRoot[u]) {
      int idx = treeRoot[v];
      int l = trees[idx].lca(v, u);
      trees[idx].invert(l, v);
      trees[idx].invert(l, u);
    } else {
      int idx = cycleP[treeRoot[v]];
      int idx2 = cycleP[treeRoot[u]];
      int len1 = abs(idx2 - idx);
      int len2 = cycle.size() - len1;
      int ll = cycle[(idx + cycle.size() - 1) % cycle.size()];
      int rr = cycle[(idx + 1) % cycle.size()];
      if (idx > idx2) swap(ll, rr);
      if (len1 < len2 || (len1 == len2 && ll > rr)) {
        if (idx > idx2) swap(idx, idx2);
        cycleTree.upd(idx + 1, idx2);
      } else {
        if (idx > idx2) swap(idx, idx2);
        if (idx > 0) cycleTree.upd(1, idx);
        cycleTree.upd(idx2 + 1, cycle.size());
      }
      trees[treeRoot[v]].invert(treeRoot[v], v);
      trees[treeRoot[u]].invert(treeRoot[u], u);
    }
    int ans = n - countEnabled;
    if (cycleTree.get(1, cycle.size()) == cycle.size()) ++ans;
    cout << ans << endl;
  }
  return 0;
}
