#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int res = 0;
  int neg;
  while (true) {
    char ch = getchar();
    if (ch >= '0' && ch <= '9' || ch == '-') {
      if (ch == '-')
        neg = -1;
      else
        neg = 1, res = ch - '0';
      break;
    }
  }
  while (true) {
    char ch = getchar();
    if (ch >= '0' && ch <= '9')
      res *= 10, res += ch - '0';
    else
      break;
  }
  return res * neg;
}
const int maxn = 100020;
const int maxx = 100000;
const int logn = 18;
const int MOd = 1e9;
int a, q, root, b, szr, cnt, gr[maxn], lasth[maxn], dad[maxn][logn], T[maxn];
int name[maxn], der[maxn], ans, ar[maxn];
int segment[maxn * 3], lazy[maxn * 3], n, bedge;
int st[maxn], at;
bool used[maxn], H[maxn], flag;
int cyc[maxn];
vector<pair<int, pair<long long, long long> > > w[maxn];
bool comp(const pair<int, pair<long long, long long> > &a,
          const pair<int, pair<long long, long long> > &b) {
  return a.second.first > b.second.first;
}
void dfs(int n, int back) {
  if (used[n]) {
    if (flag) return;
    int j = 1;
    while (st[j] != n) j++;
    root = n;
    flag = 1;
    b = st[at];
    while (j <= at) {
      cyc[st[j]] = ++szr;
      T[szr] = st[j];
      j++;
    }
    return;
  }
  st[++at] = n;
  used[n] = 1;
  for (int i = 0; i < w[n].size(); i++)
    if (w[n][i].first != back) dfs(w[n][i].first, n);
  at--;
}
int dfs3(int n, int back) {
  int ret = 1;
  for (int i = 0; i < w[n].size(); i++)
    if (w[n][i].first != back) {
      w[n][i].second.first = dfs3(w[n][i].first, n);
      ret += w[n][i].second.first;
    }
  sort(w[n].begin(), w[n].end(), comp);
  if (w[n].size() != 1 && w[n][0].second.first) H[w[n][0].first] = 1;
  return ret;
}
void dfs2(int n, int back, int g, int d, int lh) {
  if (cyc[n]) g = n;
  gr[n] = g;
  der[n] = d;
  if (!H[back] && H[n]) lh = n;
  lasth[n] = lh;
  dad[n][0] = back;
  for (int i = 1; (1 << i) <= der[n]; i++)
    dad[n][i] = dad[dad[n][i - 1]][i - 1];
  for (int i = 0; i < w[n].size(); i++)
    if (w[n][i].first != back) {
      name[w[n][i].first] = ++cnt;
      dfs2(w[n][i].first, n, g, d + 1, lh);
    }
}
void ind(int &k, int &b, int &s) {
  if (lazy[k]) {
    if (k < n) {
      lazy[2 * k] ^= 1;
      lazy[2 * k + 1] ^= 1;
    }
    segment[k] = s - b + 1 - segment[k];
    lazy[k] = 0;
  }
}
int ret(int &k, int &b, int &s) {
  if (lazy[k]) return s - b + 1 - segment[k];
  return segment[k];
}
int update(int k, int b, int s, int x, int y) {
  if (b > y || x > s) return ret(k, b, s);
  if (x <= b && s <= y) {
    lazy[k] ^= 1;
    return ret(k, b, s);
  }
  ind(k, b, s);
  segment[k] = update(2 * k, b, (b + s) / 2, x, y) +
               update(2 * k + 1, (b + s) / 2 + 1, s, x, y);
  return ret(k, b, s);
}
int find(int k, int b, int s, int x, int y) {
  if (b > y || x > s) return 0;
  if (x <= b && s <= y) return ret(k, b, s);
  ind(k, b, s);
  return find(2 * k, b, (b + s) / 2, x, y) +
         find(2 * k + 1, (b + s) / 2 + 1, s, x, y);
}
void up(int x, int y) {
  if (der[x] < der[y]) swap(x, y);
  while (der[x] > der[y]) {
    if (H[x]) {
      if (der[lasth[x]] <= der[y]) {
        update(1, 1, n, name[y] + 1, name[x]);
        break;
      } else {
        update(1, 1, n, name[lasth[x]], name[x]);
        x = dad[lasth[x]][0];
      }
    } else {
      ans += ar[name[x]] ? -1 : 1;
      ar[name[x]] ^= 1;
      x = dad[x][0];
    }
  }
}
int lca(int x, int y) {
  if (der[x] < der[y]) swap(x, y);
  for (int k = 18; k >= 0; k--)
    if ((1 << k) <= der[x] && der[dad[x][k]] > der[y]) x = dad[x][k];
  if (der[x] > der[y]) x = dad[x][0];
  for (int k = 18; k >= 0; k--)
    if ((1 << k) <= der[x] && dad[x][k] != dad[y][k])
      x = dad[x][k], y = dad[y][k];
  if (x != y) x = dad[x][0];
  return x;
}
int main() {
  scanf("%d %d", &a, &q);
  n = 1;
  while (n < a) n <<= 1;
  for (int i = 1, j, k; i <= a; i++) {
    scanf("%d %d", &j, &k);
    w[j].push_back(pair<int, pair<long long, long long> >(
        k, pair<long long, long long>(0, 0)));
    w[k].push_back(pair<int, pair<long long, long long> >(
        j, pair<long long, long long>(0, 0)));
  }
  dfs(1, 0);
  for (vector<pair<int, pair<long long, long long> > >::iterator it =
           w[root].begin();
       it != w[root].end(); it++)
    if (it->first == b) {
      w[root].erase(it);
      break;
    }
  for (vector<pair<int, pair<long long, long long> > >::iterator it =
           w[b].begin();
       it != w[b].end(); it++)
    if (it->first == root) {
      w[b].erase(it);
      break;
    }
  dfs3(root, 0);
  H[root] = 0;
  dfs2(root, 0, root, 0, 0);
  for (int i = 1, x, y; i <= q; i++) {
    scanf("%d %d", &x, &y);
    if (gr[x] != gr[y]) {
      up(x, gr[x]);
      x = gr[x];
      up(y, gr[y]);
      y = gr[y];
      int t = abs(der[x] - der[y]);
      if (2 * t < szr) up(x, y);
      if (2 * t == szr) {
        if (der[x] < der[y]) {
          int l = cyc[x] - 1, r = cyc[x] + 1;
          if (l <= 0) l += szr;
          if (r > szr) r -= szr;
          if (T[l] < T[r])
            up(root, x), up(y, b), bedge ^= 1;
          else
            up(x, y);
        } else {
          int l = cyc[x] - 1, r = cyc[x] + 1;
          if (l <= 0) l += szr;
          if (r > szr) r -= szr;
          if (T[l] > T[r])
            up(root, x), up(y, b), bedge ^= 1;
          else
            up(x, y);
        }
      }
      if (2 * t > szr) up(root, x), up(y, b), bedge ^= 1;
    } else {
      int t = lca(x, y);
      up(x, t);
      up(y, t);
    }
    int t = 0;
    if (bedge) {
      t++;
      x = b;
      while (der[x] > 0) {
        if (H[x]) {
          t += find(1, 1, n, name[lasth[x]], name[x]);
          x = dad[lasth[x]][0];
        } else {
          t += ar[name[x]];
          x = dad[x][0];
        }
      }
    }
    printf("%d\n", a - (ans + find(1, 1, n, 1, n) + bedge - (t == szr)));
  }
  return 0;
}
