#include <bits/stdc++.h>
using namespace std;
const int MOD(1000000007);
const int INF((1 << 30) - 1);
const int MAXN(100005);
vector<int> a[MAXN], cycle, d;
int n, m, visited[MAXN], par[MAXN], root[MAXN], num[MAXN], numCycle;
int nxt[MAXN], h[MAXN], idx[MAXN], removeEdgeTree, removeEdgeCycle;
;
bool isCycle[MAXN], heavy[MAXN];
struct segment_tree {
  int n;
  vector<int> t;
  vector<int> tag;
  segment_tree(int n) : n(n) {
    t.resize(4 * n);
    tag.resize(4 * n);
    t[1] = n;
    tag[1] = 1;
  }
  inline void rev(int i, int f, int l) {
    t[i] = (l - f + 1) - t[i];
    tag[i] ^= 1;
  }
  void update(int i, int f, int l, int st, int fn) {
    if (st > fn) return;
    if (f == st && l == fn) {
      rev(i, f, l);
      return;
    }
    int m = (f + l) / 2;
    if (tag[i]) {
      rev(i * 2, f, m);
      rev(i * 2 + 1, m + 1, l);
      tag[i] = 0;
    }
    if (fn <= m)
      update(i * 2, f, m, st, fn);
    else if (st > m)
      update(i * 2 + 1, m + 1, l, st, fn);
    else {
      update(i * 2, f, m, st, m);
      update(i * 2 + 1, m + 1, l, m + 1, fn);
    }
    t[i] = t[i * 2] + t[i * 2 + 1];
  }
};
vector<segment_tree> segtree;
void init() {
  for (int i = 1; i <= n; i++) {
    a[i].clear();
    visited[i] = 0;
    isCycle[i] = 0;
    heavy[i] = 0;
  }
  cycle.clear();
}
void dfs(int node) {
  visited[node] = 2;
  for (int i = 0; i < a[node].size(); i++) {
    int u = a[node][i];
    if (visited[u] == 0) {
      par[u] = node;
      dfs(u);
    } else if (visited[u] == 2 && u != par[node]) {
      int v = node;
      while (v != u) {
        cycle.push_back(v);
        isCycle[v] = 1;
        v = par[v];
      }
      cycle.push_back(u);
      isCycle[u] = 1;
    }
  }
  visited[node] = 1;
}
stack<int> st;
void dfs2(int node, int r) {
  visited[node] = 1;
  root[node] = r;
  num[node] = 1;
  st.push(node);
  d.clear();
  for (int i = 0; i < a[node].size(); i++) {
    int u = a[node][i];
    if (!visited[u] && !isCycle[u]) {
      par[u] = node;
      d.push_back(u);
      dfs2(u, r);
      num[node] += num[u];
    }
  }
  for (int i = 0; i < d.size(); i++) {
    int u = d[i];
    heavy[u] = (num[u] * 2 > num[node]);
  }
}
void modify(int u) {
  while (u != par[u]) {
    removeEdgeTree -= segtree[idx[u]].t[1];
    segtree[idx[u]].update(1, 1, segtree[idx[u]].n, 1, h[u]);
    removeEdgeTree += segtree[idx[u]].t[1];
    u = nxt[u];
  }
}
bool chk(int u, int v) {
  if (u < v) {
    int t = u - 1;
    if (t == 0) t = numCycle;
    return cycle[t - 1] < cycle[u];
  } else {
    int t = u + 1;
    if (t > numCycle) t = 1;
    return cycle[t - 1] < cycle[u - 2];
  }
}
int main() {
  scanf("%d%d", &n, &m);
  init();
  for (int i = 1; i <= n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    a[u].push_back(v);
    a[v].push_back(u);
  }
  dfs(1);
  numCycle = cycle.size();
  segtree.push_back(segment_tree(numCycle));
  for (int i = 1; i <= n; i++) visited[i] = 0;
  for (int i = 0; i < numCycle; i++) {
    int node = cycle[i];
    par[node] = node;
    dfs2(node, i + 1);
    while (!st.empty()) {
      int u = st.top();
      st.pop();
      if (isCycle[u]) break;
      if (nxt[u] != 0) continue;
      d.clear();
      if (!heavy[u]) {
        if (u != node) {
          d.push_back(u);
          u = par[u];
        }
      } else {
        while (u != cycle[i] && heavy[u]) {
          d.push_back(u);
          u = par[u];
        }
      }
      segtree.push_back(segment_tree(d.size()));
      for (int j = 0; j < d.size(); j++) {
        int v = d[j];
        nxt[v] = u;
        h[v] = d.size() - j;
        idx[v] = segtree.size() - 1;
      }
    }
  }
  removeEdgeCycle = numCycle;
  removeEdgeTree = n - numCycle;
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    modify(u);
    u = root[u];
    modify(v);
    v = root[v];
    if (u != v) {
      int len1 = abs(v - u);
      int len2 = numCycle - len1;
      if (len2 < len1 || (len2 == len1 && chk(u, v))) {
        if (u > v) swap(u, v);
        removeEdgeCycle -= segtree[0].t[1];
        segtree[0].update(1, 1, numCycle, 1, u);
        segtree[0].update(1, 1, numCycle, v + 1, numCycle);
        removeEdgeCycle += segtree[0].t[1];
      } else {
        if (u > v) swap(u, v);
        removeEdgeCycle -= segtree[0].t[1];
        segtree[0].update(1, 1, numCycle, u + 1, v);
        removeEdgeCycle += segtree[0].t[1];
      }
    }
    if (removeEdgeCycle <= 1)
      printf("%d\n", removeEdgeTree + 1);
    else
      printf("%d\n", removeEdgeTree + removeEdgeCycle);
  }
}
