#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
 public:
  vector<int> b;
  vector<int> mod;
  int n;
  SegmentTree(){};
  SegmentTree(int _n) { start(_n); }
  void start(int _n) {
    n = _n;
    b.resize(4 * n);
    mod.resize(4 * n);
    for (int i = 0; i < 4 * n; i++) b[i] = 0;
    build(1, 1, n);
  }
  void build(int v, int l, int r) {
    if (l == r) {
      b[v] = 1;
      mod[v] = -1;
    } else {
      int tm = (l + r) / 2;
      build(v * 2, l, tm);
      build(v * 2 + 1, tm + 1, r);
      b[v] = b[v * 2] + b[v * 2 + 1];
      mod[v] = -1;
    }
  }
  int get(int l, int r, int v = 1, int tl = 1, int tr = -1) {
    if (tr == -1) tr = n;
    if (l > r) return 0;
    if (tl == l && tr == r) return b[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return get(l, min(r, tm), v * 2, tl, tm) +
           get(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
  }
  void push(int v, int l, int r) {
    if (mod[v] == 1 && 2 * v + 1 < 4 * n) {
      if (mod[v * 2] != 1)
        mod[v * 2] = 1;
      else
        mod[v * 2] = -1;
      if (mod[v * 2 + 1] != 1)
        mod[v * 2 + 1] = 1;
      else
        mod[v * 2 + 1] = -1;
      int tm = (l + r) / 2;
      b[v * 2] = (tm - l + 1) - b[v * 2];
      b[v * 2 + 1] = (r - tm) - b[v * 2 + 1];
      mod[v] = -1;
    }
  }
  void Assign(int l, int r, int v = 1, int tl = 1, int tr = -1) {
    if (tr == -1) tr = n;
    if (l > r) return;
    if (l <= tl && tr <= r) {
      b[v] = (tr - tl + 1) - b[v];
      if (mod[v] != 1)
        mod[v] = 1;
      else
        mod[v] = -1;
      return;
    }
    if (tl > r || tr < l) return;
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    Assign(l, r, v * 2, tl, tm);
    Assign(l, r, v * 2 + 1, tm + 1, tr);
    b[v] = b[v * 2] + b[v * 2 + 1];
  }
};
class way {
 public:
  int boss;
  vector<int> path;
  SegmentTree ST;
  way(vector<int> v, int _boss) {
    for (int i = 0; i < (int)v.size(); i++) path.push_back(v[i]);
    boss = _boss;
    ST.start((int)v.size());
  }
  void show() {
    cout << " way : ";
    for (int i = 0; i < (int)path.size(); i++) cout << path[i] + 1 << " ";
    cout << "\n";
    cout << " boss : " << boss + 1 << "\n\n";
  }
};
vector<vector<int> > v;
vector<int> cycle;
map<int, int> mapaIndex;
map<int, bool> isInCycle;
bool used[100000 + 10];
int Own[100000];
vector<way> ways;
vector<int> p;
vector<int> heavy;
vector<int> depth;
vector<int> nxt;
vector<int> waynumber;
vector<int> leaves;
vector<int> localway;
vector<pair<int, int> > edgesST;
int localboss;
int endCycle;
bool isCycle;
int color;
int c;
int edges;
int maxi;
int treeEdges;
int cycleEdges;
void dfsHLD(int n, int par = -1) {
  p[n] = par;
  heavy[n] = 1;
  for (int i = 0; i < (int)v[n].size(); i++) {
    int to = v[n][i];
    if (to == par || Own[to] != color) continue;
    depth[to] = depth[n] + 1;
    dfsHLD(to, n);
    heavy[n] += heavy[to];
    if (nxt[n] == -1 || heavy[to] > heavy[nxt[n]]) nxt[n] = to;
  }
  if (n != color && v[n].size() == 1) leaves.push_back(n);
}
void dfsWay(int n) {
  localway.push_back(n);
  waynumber[n] = c;
  edgesST[n].first = edges;
  if (edges == -1)
    edges = 1;
  else
    edges++;
  edgesST[n].second = edges;
  if (nxt[p[n]] == n) {
    dfsWay(p[n]);
  } else {
    way w(localway, p[n]);
    ways.push_back(w);
    c++;
  }
}
void dfsTree(int n) {
  used[n] = true;
  Own[n] = color;
  for (int i = 0; i < (int)v[n].size(); i++)
    if (!used[v[n][i]]) dfsTree(v[n][i]);
}
bool dfs(int n, int par = -1) {
  used[n] = 1;
  bool win = false;
  for (int i = 0; i < (int)v[n].size(); i++) {
    int to = v[n][i];
    if (to == par) continue;
    if (used[to]) {
      win = true;
      if (endCycle == -1) endCycle = to;
    } else
      win = win || dfs(to, n);
  }
  if (win) cycle.push_back(n);
  if (n == endCycle) win = false;
  return win;
}
bool f(int A, int B, bool is) {
  int N = (int)cycle.size();
  int t1 = (mapaIndex[A] - mapaIndex[B] + N) % N;
  int t2 = (mapaIndex[B] - mapaIndex[A] + N) % N;
  if (t1 < t2) return true;
  if (t2 < t1) return false;
  if (is) {
    if (cycle[(mapaIndex[B] - 1 + N) % N] < cycle[(mapaIndex[B] + 1) % N])
      return false;
    return true;
  }
  if (cycle[(mapaIndex[A] - 1 + N) % N] < cycle[(mapaIndex[A] + 1) % N])
    return true;
  return false;
}
void UP(int a, int b) {
  int x = a;
  while (true) {
    if (x == b) return;
    if (waynumber[x] == waynumber[b]) {
      int Was = ways[waynumber[x]].ST.get(1, ways[waynumber[x]].ST.n);
      ways[waynumber[x]].ST.Assign(edgesST[x].second, edgesST[b].first);
      int Now = ways[waynumber[x]].ST.get(1, ways[waynumber[x]].ST.n);
      int Delta = Now - Was;
      treeEdges += Delta;
      break;
    }
    int Was = ways[waynumber[x]].ST.get(1, ways[waynumber[x]].ST.n);
    ways[waynumber[x]].ST.Assign(edgesST[x].second, ways[waynumber[x]].ST.n);
    int Now = ways[waynumber[x]].ST.get(1, ways[waynumber[x]].ST.n);
    int Delta = Now - Was;
    treeEdges += Delta;
    x = ways[waynumber[x]].boss;
  }
}
int lca(int a, int b) {
  if (a == b) return a;
  int x = a;
  int y = b;
  while (true) {
    if (waynumber[x] == waynumber[y]) {
      if (depth[x] < depth[y]) return x;
      return y;
    }
    if (depth[ways[waynumber[x]].boss] >= depth[ways[waynumber[y]].boss])
      x = ways[waynumber[x]].boss;
    else {
      y = ways[waynumber[y]].boss;
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  v.resize(n);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  endCycle = -1;
  for (int i = 0; i < 100000; i++) used[i] = false;
  dfs(0);
  if (cycle.size() == 0)
    isCycle = false;
  else
    isCycle = true;
  for (int i = 0; i < (int)cycle.size(); i++) {
    mapaIndex[cycle[i]] = i;
    isInCycle[cycle[i]] = true;
  }
  for (int i = 0; i < 100000; i++) used[i] = false;
  for (int i = 0; i < (int)cycle.size(); i++) {
    Own[cycle[i]] = cycle[i];
    used[cycle[i]] = true;
    if ((int)v[cycle[i]].size() == 2) continue;
    int to;
    color = cycle[i];
    for (int j = 0; j < (int)v[cycle[i]].size(); j++)
      if (!isInCycle[v[cycle[i]][j]]) {
        to = v[cycle[i]][j];
        dfsTree(to);
      }
  }
  maxi = n + 1;
  p.resize(maxi);
  heavy.resize(maxi);
  depth.resize(maxi);
  nxt.resize(maxi);
  waynumber.resize(maxi);
  for (int i = 0; i < maxi; i++) {
    used[i] = false;
    p[i] = -1;
    heavy[i] = -1;
    depth[i] = 0;
    nxt[i] = -1;
    waynumber[i] = -1;
  }
  c = 0;
  edgesST.resize(n);
  for (int i = 0; i < (int)cycle.size(); i++) {
    color = cycle[i];
    dfsHLD(cycle[i]);
    p[cycle[i]] = cycle[i];
    for (int i = 0; i < (int)leaves.size(); i++) {
      edges = -1;
      dfsWay(leaves[i]);
      localway.clear();
    }
    leaves.clear();
    if (waynumber[cycle[i]] == -1) continue;
    p[cycle[i]] = maxi - 1;
    ways[waynumber[cycle[i]]].boss = maxi - 1;
    depth[maxi - 1] = -1000000000;
  }
  vector<int> ans;
  SegmentTree CycleST((int)cycle.size());
  cycleEdges = (int)cycle.size();
  treeEdges = n - cycleEdges;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (Own[a] == Own[b]) {
      int lcantrop = lca(a, b);
      UP(a, lcantrop);
      UP(b, lcantrop);
    } else {
      UP(a, Own[a]);
      UP(b, Own[b]);
      bool isSwapped = false;
      if (mapaIndex[Own[a]] > mapaIndex[Own[b]]) {
        swap(a, b);
        isSwapped = true;
      }
      bool left = f(Own[a], Own[b], isSwapped);
      if (left) {
        int Was = CycleST.get(1, (int)cycle.size());
        if (mapaIndex[Own[a]] > 0) CycleST.Assign(1, mapaIndex[Own[a]]);
        CycleST.Assign(mapaIndex[Own[b]] + 1, (int)cycle.size());
        int Now = CycleST.get(1, (int)cycle.size());
        int Delta = Now - Was;
        cycleEdges += Delta;
      } else {
        int Was = CycleST.get(1, (int)cycle.size());
        CycleST.Assign(mapaIndex[Own[a]] + 1, mapaIndex[Own[b]]);
        int Now = CycleST.get(1, (int)cycle.size());
        int Delta = Now - Was;
        cycleEdges += Delta;
      }
    }
    ans.push_back(max(cycleEdges, 1) + treeEdges);
  }
  for (int i = 0; i < (int)ans.size(); i++) cout << ans[i] << "\n";
  return 0;
}
