#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int INF = 2000000000;
const long long BIG = 1446803456761533460LL;
const int maxn = 100010;
int N, M, C;
int st[maxn], cyc[maxn], icyc[maxn], ht[maxn], sz[maxn], par[maxn], head[maxn],
    rot[maxn];
vector<int> g[maxn], subt[maxn];
bool vis[maxn];
struct Segment {
  int seg[maxn * 4];
  bool lazy[maxn * 4];
  void apply(int x, int l, int r) {
    seg[x] = r - l - seg[x];
    lazy[x] ^= 1;
  }
  void push(int x, int l, int r) {
    apply((x << 1), l, ((l + r) >> 1));
    apply(((x << 1) | 1), ((l + r) >> 1), r);
    lazy[x] = 0;
  }
  void update(int li, int ri, int x = 1, int l = 0, int r = N) {
    if (li >= r || l >= ri) {
    } else if (li <= l && r <= ri) {
      apply(x, l, r);
    } else {
      if (lazy[x]) push(x, l, r);
      update(li, ri, (x << 1), l, ((l + r) >> 1));
      update(li, ri, ((x << 1) | 1), ((l + r) >> 1), r);
      seg[x] = seg[(x << 1)] + seg[((x << 1) | 1)];
    }
  }
  int get() { return seg[1]; }
} segtree, segcyc;
int dfs_cyc(int x, int parx) {
  if (vis[x]) return x;
  vis[x] = 1;
  for (auto y : g[x])
    if (y != parx) {
      int v;
      if ((v = dfs_cyc(y, x)) != -1) {
        if (v == -2) return -2;
        icyc[y] = C;
        cyc[C++] = y;
        if (x != v)
          return v;
        else
          return -2;
      }
    }
  return -1;
}
void dfs_sz(int x, int parx) {
  sz[x] = 1;
  for (auto y : g[x])
    if (y != parx && icyc[y] == -1) {
      dfs_sz(y, x);
      subt[x].emplace_back(y);
      sz[x] += sz[y];
    }
}
int tim;
void dfs_hld(int x) {
  st[x] = tim++;
  sort((subt[x]).begin(), (subt[x]).end(),
       [](int a, int b) { return sz[a] > sz[b]; });
  for (int i = 0; i < subt[x].size(); ++i) {
    int y = subt[x][i];
    par[y] = x;
    head[y] = i == 0 ? head[x] : y;
    ht[y] = ht[x] + 1;
    rot[y] = rot[x];
    dfs_hld(y);
  }
}
int get_lca(int a, int b) {
  while (head[a] != head[b]) {
    if (ht[head[a]] > ht[head[b]]) swap(a, b);
    b = par[head[b]];
  }
  if (ht[a] > ht[b]) swap(a, b);
  return a;
}
void toggle_path(int a, int b) {
  while (head[a] != head[b]) {
    segtree.update(st[head[b]], st[b] + 1);
    b = par[head[b]];
  }
  segtree.update(st[a] + 1, st[b] + 1);
}
int comp_cnt() {
  return N - segtree.get() - segcyc.get() + (segcyc.get() == C);
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  memset(icyc, -1, sizeof icyc);
  cin >> N >> M;
  for (int i = 0; i < N; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b), g[b].emplace_back(a);
  }
  dfs_cyc(0, 0);
  tim = 0;
  for (int i = 0; i < C; ++i) {
    dfs_sz(cyc[i], -1);
    head[cyc[i]] = cyc[i];
    rot[cyc[i]] = cyc[i];
    dfs_hld(cyc[i]);
  }
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    int ra = rot[a], rb = rot[b];
    if (ra == rb) {
      int c = get_lca(a, b);
      toggle_path(c, a);
      toggle_path(c, b);
    } else {
      toggle_path(ra, a);
      toggle_path(rb, b);
      int ca = icyc[ra], cb = icyc[rb];
      bool flag = ca > cb;
      if (flag) swap(ca, cb);
      bool out = false;
      int d = cb - ca;
      if (d > C - d)
        out = true;
      else if (d == C - d) {
        if (!flag)
          out = cyc[(ca - 1 + C) % C] < cyc[(ca + 1) % C];
        else
          out = cyc[(cb + 1) % C] < cyc[(cb - 1 + C) % C];
      }
      if (out)
        segcyc.update(0, ca), segcyc.update(cb, C);
      else
        segcyc.update(ca, cb);
    }
    cout << comp_cnt() << '\n';
  }
}
