#include <bits/stdc++.h>
using namespace std;
struct segment_tree {
  vector<int> tree;
  vector<int> rev;
  int n;
  segment_tree() {}
  segment_tree(int n_) {
    n = n_;
    tree.resize(4 * n);
    rev.resize(4 * n);
  }
  void push(int v, int tl, int tr) {
    if (rev[v] == 0) return;
    tree[v] = (tr - tl) - tree[v];
    if (tl + 1 != tr) {
      rev[2 * v + 1] = 1 - rev[2 * v + 1];
      rev[2 * v + 2] = 1 - rev[2 * v + 2];
    }
    rev[v] = 0;
  }
  void upd(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) {
      push(v, tl, tr);
      return;
    }
    if (tl >= l && tr <= r) {
      rev[v] = 1 - rev[v];
      push(v, tl, tr);
      return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    upd(2 * v + 1, tl, tm, l, r);
    upd(2 * v + 2, tm, tr, l, r);
    tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
  }
  void upd(int l, int r) { upd(0, 0, n, l, r + 1); }
  int get(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tl >= r || tr <= l) return 0;
    if (tl >= l && tr <= r) return tree[v];
    int tm = (tl + tr) / 2;
    return get(2 * v + 1, tl, tm, l, r) + get(2 * v + 2, tm, tr, l, r);
  }
  int get(int a, int b) { return get(0, 0, n, a, b + 1); }
};
struct hld {
  int n;
  vector<vector<int>> g;
  int koren;
  vector<int> mas;
  vector<int> key;
  vector<int> tout;
  vector<int> lider;
  vector<int> pred;
  segment_tree tree;
  void dfs_mas(int u, int p) {
    mas[u] = 1;
    for (auto i : g[u]) {
      if (i == p) continue;
      dfs_mas(i, u);
      mas[u] += mas[i];
    }
  }
  int tmr;
  void dfs_key(int u, int p, int lid) {
    key[u] = tmr++;
    pred[key[u]] = key[p];
    lider[key[u]] = lid;
    int mxs = 0;
    int num = -1;
    for (auto i : g[u]) {
      if (i == p) continue;
      if (mas[i] > mxs) {
        num = i;
        mxs = mas[i];
      }
    }
    if (num == -1) {
      tout[key[u]] = tmr;
      return;
    }
    dfs_key(num, u, lid);
    for (auto i : g[u]) {
      if (i == p || i == num) continue;
      dfs_key(i, u, tmr);
    }
    tout[key[u]] = tmr;
  }
  bool predok(int a, int b) { return a <= b && tout[a] >= tout[b]; }
  void build() {
    mas.resize(n);
    key.resize(n);
    tout.resize(n);
    lider.resize(n);
    pred.resize(n);
    dfs_mas(koren, koren);
    tmr = 0;
    dfs_key(koren, koren, 0);
    tree = segment_tree(n);
  }
  int upd(int a, int b) {
    a = key[a];
    b = key[b];
    int ans = 0;
    while (!predok(lider[a], b)) {
      ans += (a - lider[a] + 1) - 2 * tree.get(lider[a], a);
      tree.upd(lider[a], a);
      a = pred[lider[a]];
    }
    while (!predok(lider[b], a)) {
      ans += (b - lider[b] + 1) - 2 * tree.get(lider[b], b);
      tree.upd(lider[b], b);
      b = pred[lider[b]];
    }
    if (a > b) swap(a, b);
    ans += (b - a) - 2 * tree.get(a + 1, b);
    tree.upd(a + 1, b);
    return ans;
  }
  hld() {}
  hld(vector<vector<int>> g_, int koren_) {
    g = g_;
    koren = koren_;
    n = g.size();
    build();
  }
};
int n, m;
vector<vector<int>> g;
vector<int> used;
vector<int> cycle;
int finded = -1;
void dfs_cycle(int u, int p) {
  if (used[u] == 1) {
    finded = u;
    cycle.push_back(u);
    return;
  }
  used[u] = 1;
  for (auto i : g[u]) {
    if (i == p) continue;
    dfs_cycle(i, u);
    if (finded == -2) return;
    if (finded == u) {
      finded = -2;
      return;
    }
    if (finded >= 0) {
      cycle.push_back(u);
      return;
    }
  }
}
int s;
vector<hld> trees;
vector<vector<vector<int>>> g_t;
vector<int> tree_num;
vector<int> inside_num;
int tmr;
void dfs_build(int u, int p, int t_n, int l, int r, vector<vector<int>>& g1) {
  tree_num[u] = t_n;
  inside_num[u] = tmr++;
  g1.push_back(vector<int>(0));
  for (auto i : g[u]) {
    if (i == p || i == l || i == r) continue;
    g1[inside_num[u]].push_back(tmr);
    dfs_build(i, u, t_n, l, r, g1);
  }
}
segment_tree s_t_cycle;
void build() {}
int rebro_cnt;
int cycle_cnt;
void solve() {
  scanf("%d %d", &n, &m);
  g.resize(n);
  int a, b;
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a, &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  used.resize(n);
  dfs_cycle(0, 0);
  tree_num.resize(n);
  inside_num.resize(n);
  s = cycle.size();
  g_t.resize(s);
  for (int i = 0; i < s; i++) {
    int l, r;
    l = cycle[(i + s - 1) % s];
    r = cycle[(i + 1) % s];
    tmr = 0;
    dfs_build(cycle[i], cycle[i], i, l, r, g_t[i]);
  }
  trees.resize(s);
  for (int i = 0; i < s; i++) trees[i] = hld(g_t[i], 0);
  s_t_cycle = segment_tree(s);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    a--;
    b--;
    int t1 = tree_num[a];
    int t2 = tree_num[b];
    if (t1 == t2) {
      rebro_cnt += trees[t1].upd(inside_num[a], inside_num[b]);
    } else {
      rebro_cnt += trees[t1].upd(inside_num[a], 0);
      rebro_cnt += trees[t2].upd(inside_num[b], 0);
      int num_work;
      if (cycle[(t1 + 1) % s] < cycle[(t1 - 1 + s) % s]) {
        num_work = 1;
      } else {
        num_work = 2;
      }
      if (t1 > t2) {
        swap(t1, t2);
        num_work = 3 - num_work;
      }
      if ((t2 - t1) * 2 < s) {
        num_work = 1;
      } else if ((t2 - t1) * 2 > s) {
        num_work = 2;
      }
      if (num_work == 1) {
        s_t_cycle.upd(t1, t2 - 1);
      } else {
        s_t_cycle.upd(0, t1 - 1);
        s_t_cycle.upd(t2, s - 1);
      }
      cycle_cnt = s_t_cycle.get(0, s - 1);
    }
    int ans = n - rebro_cnt;
    if (cycle_cnt == s) {
      ans -= (s - 1);
    } else {
      ans -= cycle_cnt;
    }
    printf("%d\n", ans);
  }
}
int main() {
  solve();
  return 0;
}
