#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 15;
vector<int> adj[maxn];
vector<int> cycle_nodes;
pair<int, int> in_cycle = make_pair(-1, -1);
int sz[maxn], big_daddy[maxn], par[maxn], st[maxn], en[maxn], cycle_pos[maxn];
bool mark[maxn];
int tim = 0, n, m;
bool EX = 0;
int CYseg[4 * maxn], CYlazy[4 * maxn];
void CYsag(int id, int S) {
  CYseg[id] = S - CYseg[id];
  CYlazy[id] = !CYlazy[id];
}
void CYshift(int id, int L, int R) {
  if (!CYlazy[id]) return;
  CYlazy[id] = 0;
  int mid = (L + R) >> 1;
  int p1 = mid - L;
  int p2 = R - mid;
  CYsag(id * 2, p1);
  CYsag(id * 2 + 1, p2);
}
void update_cycle_part(int l, int r, int L = 0, int R = n, int id = 1) {
  if (r <= L or R <= l) return;
  if (l <= L and R <= r) return CYsag(id, R - L);
  int mid = (L + R) >> 1;
  CYshift(id, L, R);
  update_cycle_part(l, r, L, mid, id * 2);
  update_cycle_part(l, r, mid, R, id * 2 + 1);
  CYseg[id] = CYseg[id * 2] + CYseg[id * 2 + 1];
}
int get_cycle_cnt(int l, int r, int L = 0, int R = n, int id = 1) {
  if (r <= L or R <= l) return 0;
  if (l <= L and R <= r) return CYseg[id];
  CYshift(id, L, R);
  int mid = (L + R) >> 1;
  int A = get_cycle_cnt(l, r, L, mid, id * 2);
  int B = get_cycle_cnt(l, r, mid, R, id * 2 + 1);
  return A + B;
}
int seg[4 * maxn], lazy[4 * maxn];
void sag(int id, int S) {
  seg[id] = S - seg[id];
  lazy[id] = !lazy[id];
}
void shift(int id, int L, int R) {
  if (!lazy[id]) return;
  lazy[id] = 0;
  int mid = (L + R) >> 1;
  int p1 = mid - L;
  int p2 = R - mid;
  sag(id * 2, p1);
  sag(id * 2 + 1, p2);
}
void update(int l, int r, int L = 0, int R = n, int id = 1) {
  if (r <= L or R <= l) return;
  if (l <= L and R <= r) return sag(id, R - L);
  int mid = (L + R) >> 1;
  shift(id, L, R);
  update(l, r, L, mid, id * 2);
  update(l, r, mid, R, id * 2 + 1);
  seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
int get_cnt(int l, int r, int L = 0, int R = n, int id = 1) {
  if (r <= L or R <= l) return 0;
  if (l <= L and R <= r) return seg[id];
  shift(id, L, R);
  int mid = (L + R) >> 1;
  int A = get_cnt(l, r, L, mid, id * 2);
  int B = get_cnt(l, r, mid, R, id * 2 + 1);
  return A + B;
}
void make_cycle() {
  int u = in_cycle.first;
  int v = in_cycle.second;
  fill(mark, mark + maxn, 0);
  while (v != u) {
    cycle_pos[v] = cycle_nodes.size();
    cycle_nodes.push_back(v);
    mark[v] = true;
    v = par[v];
  }
  mark[u] = true;
  cycle_pos[u] = cycle_nodes.size();
  cycle_nodes.push_back(v);
}
void find_cycle(int v = 0, int p = 0) {
  mark[v] = true;
  par[v] = p;
  for (auto u : adj[v]) {
    if (u == p) continue;
    if (mark[u] and in_cycle == make_pair(-1, -1)) in_cycle = make_pair(u, v);
    if (!mark[u]) find_cycle(u, v);
  }
}
int making_sz(int v, int p) {
  big_daddy[v] = v;
  par[v] = p;
  cycle_pos[v] = cycle_pos[p];
  for (auto u : adj[v])
    if (u != p and !mark[u]) sz[v] += making_sz(u, v);
  return ++sz[v];
}
void initiate_sz_makin() {
  for (auto v : cycle_nodes) making_sz(v, v);
}
bool size_cmp(int u, int v) { return sz[u] > sz[v]; }
void dfs(int v, int p) {
  mark[v] = true;
  st[v] = tim++;
  bool c = true;
  sort((adj[v]).begin(), (adj[v]).end(), size_cmp);
  for (auto u : adj[v]) {
    if (mark[u]) continue;
    if (c) {
      c = false;
      big_daddy[u] = v;
    }
    dfs(u, v);
  }
  en[v] = tim;
}
void initiate_DFS() {
  for (auto v : cycle_nodes) dfs(v, v);
}
void pre_solve() {
  find_cycle();
  make_cycle();
  initiate_sz_makin();
  initiate_DFS();
}
void add_edge(int u, int v) {
  adj[v].push_back(u);
  adj[u].push_back(v);
}
void input() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    add_edge(a, b);
  }
}
bool time_cmp(int u, int v) { return st[u] >= st[v]; }
int LCA(int u, int v) {
  while (big_daddy[u] != big_daddy[v]) {
    if (time_cmp(u, v)) swap(u, v);
    v = par[big_daddy[v]];
  }
  if (st[u] < st[v]) swap(u, v);
  return v;
}
int nxt(int u, int v) {
  if (u == 0) {
    return cycle_nodes[cycle_nodes.size() - 1] <
           cycle_nodes[(u + 1) % cycle_nodes.size()];
  }
  return cycle_nodes[u - 1] < cycle_nodes[(u + 1) % cycle_nodes.size()];
}
void fricker(int u, int v) {
  int mini = min(u, v);
  int maxi = max(u, v);
  int sz = cycle_nodes.size();
  update_cycle_part(mini, maxi);
  if (maxi - mini > (sz - (maxi - mini)) or
      (maxi - mini == sz - (maxi - mini) and !(nxt(u, v) ^ (u <= v)))) {
    update_cycle_part(0, sz - 1);
    EX = !EX;
  }
}
void update_till_daddy(int u, int D) {
  while (big_daddy[u] != big_daddy[D]) {
    update(st[big_daddy[u]], st[u] + 1);
    u = par[big_daddy[u]];
  }
  update(st[D] + 1, st[u] + 1);
}
void updt_tree(int u, int v) {
  int z = LCA(u, v);
  update_till_daddy(u, z);
  update_till_daddy(v, z);
}
int ANS = 0;
void quer(int u, int v) {
  int A = cycle_nodes[cycle_pos[u]];
  int B = cycle_nodes[cycle_pos[v]];
  ANS -= get_cnt(st[A], en[A]);
  if (A != B) ANS -= get_cnt(st[B], en[B]);
  if (cycle_pos[u] == cycle_pos[v])
    updt_tree(u, v);
  else {
    updt_tree(u, cycle_nodes[cycle_pos[u]]);
    updt_tree(v, cycle_nodes[cycle_pos[v]]);
    fricker(cycle_pos[u], cycle_pos[v]);
  }
  ANS += get_cnt(st[A], en[A]);
  if (A != B) ANS += get_cnt(st[B], en[B]);
}
int answer() {
  int a = get_cycle_cnt(0, cycle_nodes.size());
  if (a < cycle_nodes.size() - 1 and EX) a++;
  a += ANS;
  return n - a;
}
void solve() {
  while (m--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    quer(u, v);
    cout << answer() << '\n';
    cout << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  input();
  pre_solve();
  solve();
}
