#include <bits/stdc++.h>
#pragma comment(linker, "/stack=64000000")
using namespace std;
const long double EPS = 1E-5;
const int INF = 1E9;
const int NMAX = 100500;
const int LOG = 20;
int n, m, cur_cc;
vector<vector<int> > g;
vector<int> path, used, cycle, cnt, cc, in_cycle;
void dfs(int v, int p) {
  used[v] = (int)(path).size();
  path.push_back(v);
  for (int i = 0; i < (int)(int)(g[v]).size(); i++) {
    int to = g[v][i];
    if (used[to] > 0 && to != p) {
      for (int j = (int)used[to]; j < (int)(int)(path).size(); j++)
        cycle.push_back(path[j]);
    }
    if (used[to] == 0) dfs(to, v);
  }
  used[v] = -1;
  path.pop_back();
}
int h[NMAX];
void go(int v) {
  cnt[v] = 1;
  cc[v] = cur_cc;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i];
    if (!cnt[to]) {
      h[to] = h[v] + 1;
      go(to);
      cnt[v] += cnt[to];
    }
  }
}
int wh[NMAX], pos[NMAX], top[NMAX], path_cnt = 0;
vector<vector<int> > mdt, push;
void heavy_light(int v) {
  bool heavy = false;
  if (wh[v] == -1) wh[v] = path_cnt;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i];
    if (wh[to] != -1 || in_cycle[to]) continue;
    if (in_cycle[v] || cnt[to] < (cnt[v] + 1) / 2) {
      wh[to] = path_cnt++;
      top[path_cnt - 1] = v;
      pos[to] = 1;
      mdt.push_back(vector<int>(0));
      push.push_back(vector<int>(0));
      heavy_light(to);
      continue;
    }
    heavy = true;
    wh[to] = wh[v];
    pos[to] = pos[v] + 1;
    heavy_light(to);
  }
  if (!heavy && !in_cycle[v]) {
    mdt[wh[v]].resize(pos[v] * 4);
    push[wh[v]].resize(pos[v] * 4);
  }
}
int inverse(int path, int v, int l, int r, int x, int y) {
  if (push[path][v]) {
    mdt[path][v] = r - l + 1 - mdt[path][v];
    push[path][v] = 0;
    if (l != r) {
      push[path][v * 2] ^= 1;
      push[path][v * 2 + 1] ^= 1;
    }
  }
  if (l == x && r == y) {
    mdt[path][v] = r - l + 1 - mdt[path][v];
    if (l != r) {
      push[path][v * 2] ^= 1;
      push[path][v * 2 + 1] ^= 1;
    }
    return r - l + 1 - 2 * mdt[path][v];
  }
  int mid = (l + r) >> 1, res = 0;
  if (x <= mid) res += inverse(path, v * 2, l, mid, x, min(y, mid));
  if (y > mid) res += inverse(path, v * 2 + 1, mid + 1, r, max(x, mid + 1), y);
  mdt[path][v] -= res;
  return res;
}
int update(int v1, int v2) {
  int ans = 0;
  while (wh[v1] != wh[v2]) {
    if (h[v1] < h[v2]) swap(v1, v2);
    ans += inverse(wh[v1], 1, 0, (int)(mdt[wh[v1]]).size() / 4 - 1, 0,
                   pos[v1] - 1);
    v1 = top[wh[v1]];
  }
  if (h[v1] < h[v2]) swap(v1, v2);
  if (v1 != v2)
    ans += inverse(wh[v1], 1, 0, (int)(mdt[wh[v1]]).size() / 4 - 1, pos[v2],
                   pos[v1] - 1);
  return ans;
}
int main() {
  cin >> n >> m;
  g.resize(n);
  for (int i = 0; i < (int)n; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    v1--;
    v2--;
    g[v1].push_back(v2);
    g[v2].push_back(v1);
  }
  used.assign(n, 0);
  dfs(0, 0);
  in_cycle.assign(n, 0);
  for (int i = 0; i < (int)(int)(cycle).size(); i++) in_cycle[cycle[i]] = i + 1;
  cnt.assign(n, 0);
  for (int i = 0; i < (int)(int)(cycle).size(); i++) cnt[cycle[i]] = 1;
  cur_cc = 0;
  cc.assign(n, -1);
  for (int i = 0; i < (int)(int)(cycle).size(); i++) {
    go(cycle[i]);
    cur_cc++;
  }
  memset(wh, -1, sizeof wh);
  for (int i = 0; i < (int)(int)(cycle).size(); i++) heavy_light(cycle[i]);
  int ans = n - (int)(cycle).size(), ans_cycle = (int)(cycle).size();
  mdt.push_back(vector<int>((int)(cycle).size() * 4));
  push.push_back(vector<int>((int)(cycle).size() * 4));
  path_cnt++;
  for (int i = 0; i < (int)m; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    v1--;
    v2--;
    if (cc[v1] == cc[v2]) {
      ans += update(v1, v2);
    } else {
      if (v1 != cycle[cc[v1]]) ans += update(v1, cycle[cc[v1]]);
      if (v2 != cycle[cc[v2]]) ans += update(v2, cycle[cc[v2]]);
      if (2 * abs(cc[v1] - cc[v2]) < (int)(cycle).size()) {
        if (cc[v1] > cc[v2]) swap(v1, v2);
        ans_cycle += inverse(path_cnt - 1, 1, 0, (int)(cycle).size() - 1,
                             cc[v1], cc[v2] - 1);
      } else if (2 * abs(cc[v1] - cc[v2]) > (int)(cycle).size()) {
        if (cc[v1] > cc[v2]) swap(v1, v2);
        if (cc[v1])
          ans_cycle += inverse(path_cnt - 1, 1, 0, (int)(cycle).size() - 1, 0,
                               cc[v1] - 1);
        ans_cycle += inverse(path_cnt - 1, 1, 0, (int)(cycle).size() - 1,
                             cc[v2], (int)(cycle).size() - 1);
      } else {
        if ((cycle[(cc[v1] + 1) % (int)(cycle).size()] <
             cycle[(cc[v1] - 1 + (int)(cycle).size()) % (int)(cycle).size()]) ^
            (cc[v1] > cc[v2])) {
          if (cc[v1] > cc[v2]) swap(v1, v2);
          ans_cycle += inverse(path_cnt - 1, 1, 0, (int)(cycle).size() - 1,
                               cc[v1], cc[v2] - 1);
        } else {
          if (cc[v1] > cc[v2]) swap(v1, v2);
          if (cc[v1])
            ans_cycle += inverse(path_cnt - 1, 1, 0, (int)(cycle).size() - 1, 0,
                                 cc[v1] - 1);
          ans_cycle += inverse(path_cnt - 1, 1, 0, (int)(cycle).size() - 1,
                               cc[v2], (int)(cycle).size() - 1);
        }
      }
    }
    if (ans_cycle == 0)
      cout << ans + 1 << endl;
    else
      cout << ans + ans_cycle << endl;
  }
}
