#include <bits/stdc++.h>
using namespace std;
vector<long long int> E[100005];
long long int end_num[100005];
long long int depth[100005];
long long int pr[100005];
long long int num_pr[100005];
long long int COUNT = 1;
long long int NUM[100005];
long long int loop_num[100005];
long long int loop_start;
long long int loop_end;
long long int N = 1;
struct _st {
  long long int num, rev, sum, loop;
} st[100005 * 4];
vector<pair<long long int, long long int> > d_vec;
long long int init_pr(long long int pos, long long int parent = -1) {
  if (pr[pos] == (1ll << (long long int)(60))) return pr[pos] = pos;
  pr[pos] = (1ll << (long long int)(60));
  for (long long int i = 0;
       i < ((long long int)(((long long int)(E[pos]).size()))); ++i)
    if (E[pos][i] != parent) {
      long long int tmp = init_pr(E[pos][i], pos);
      if (tmp != -1) return ((pr[pos] = pos) == tmp) ? -1 : tmp;
    }
  pr[pos] = -1;
  return -1;
}
long long int alloc_num(long long int pos) {
  if (num_pr[pos] != -1) return pos;
  if (depth[pos] == 0) return pos;
  NUM[pos] = COUNT++;
  for (long long int i = 0;
       i < ((long long int)(((long long int)(E[pos]).size()))); ++i)
    if (depth[E[pos][i]] < depth[pos])
      return num_pr[pos] = alloc_num(E[pos][i]);
}
void alloc_loop_num(long long int pos) {
  if (loop_num[pos] != -1) return;
  if (depth[pos] != 0) return;
  loop_num[pos] = COUNT++;
  loop_end = COUNT;
  for (long long int i = 0;
       i < ((long long int)(((long long int)(E[pos]).size()))); ++i)
    if (depth[E[pos][i]] == 0) alloc_loop_num(E[pos][i]);
  loop_start = loop_num[pos];
}
long long int dis(long long int t0, long long int t1) {
  if (loop_num[t0] < loop_num[t1]) return loop_num[t1] - loop_num[t0];
  return (loop_end - loop_start) - (loop_num[t0] - loop_num[t1]);
}
void init_loop_sum(long long int v, long long int left, long long int right) {
  if (left + 1 == right) {
    st[v].sum = (loop_start <= left && left < loop_end) ? 1 : 0;
    return;
  }
  long long int mid = (left + right) / 2;
  init_loop_sum(v * 2, left, mid);
  init_loop_sum(v * 2 + 1, mid, right);
  st[v].sum = st[v * 2].sum + st[v * 2 + 1].sum;
}
void add(long long int v, long long int flag, long long int left,
         long long int right, long long int LEFT, long long int RIGHT) {
  if (right <= left || RIGHT <= LEFT) return;
  if (!flag) {
    add(v, !flag, left, right, 0, LEFT);
    add(v, !flag, left, right, RIGHT, N);
    return;
  }
  if (right <= LEFT || RIGHT <= left) return;
  if (LEFT <= left && right <= RIGHT) {
    st[v].num = (right - left) - st[v].num;
    st[v].rev = 1 - st[v].rev;
    st[v].loop = st[v].sum - st[v].loop;
    return;
  }
  long long int mid = (left + right) / 2;
  add(v * 2, flag ^ st[v].rev, left, mid, LEFT, RIGHT);
  add(v * 2 + 1, flag ^ st[v].rev, mid, right, LEFT, RIGHT);
  st[v].num = st[v * 2].num + st[v * 2 + 1].num;
  st[v].rev = false;
  st[v].loop = st[v * 2].loop + st[v * 2 + 1].loop;
}
void init_depth(long long int pos, long long int d = 0,
                long long int parent = -1) {
  if (depth[pos] != -1) return;
  depth[pos] = d;
  if (pr[pos] == pos) depth[pos] = 0;
  if (pr[pos] == -1) pr[pos] = parent;
  for (long long int i = 0;
       i < ((long long int)(((long long int)(E[pos]).size()))); ++i)
    init_depth(E[pos][i], depth[pos] + 1, pr[pos]);
}
int main() {
  long long int n, m, t0, t1;
  cin >> n >> m;
  memset(depth, -1, sizeof(depth));
  memset(pr, -1, sizeof(pr));
  memset(num_pr, -1, sizeof(num_pr));
  memset(loop_num, -1, sizeof(loop_num));
  memset(NUM, -1, sizeof(NUM));
  for (long long int i = 0; i < ((long long int)(n)); ++i) {
    cin >> t0 >> t1;
    t0--;
    t1--;
    E[t0].push_back(t1);
    E[t1].push_back(t0);
  }
  init_pr(0);
  for (long long int i = 0; i < ((long long int)(n)); ++i)
    if (pr[i] == i && depth[i] == -1) init_depth(i);
  for (long long int i = 0; i < ((long long int)(n)); ++i)
    d_vec.push_back(make_pair(depth[i], i));
  sort(d_vec.begin(), d_vec.end());
  reverse(d_vec.begin(), d_vec.end());
  for (long long int i = 0; i < ((long long int)(n)); ++i)
    alloc_num(d_vec[i].second);
  for (long long int i = 0; i < ((long long int)(n)); ++i)
    if (loop_num[i] == -1 && depth[i] == 0) alloc_loop_num(i);
  while (N < 100005) N *= 2;
  for (long long int i = 0; i < ((long long int)(100005 * 4)); ++i)
    st[i].rev = st[i].num = st[i].loop = 0;
  init_loop_sum(1, 0, N);
  for (long long int stage = 0; stage < ((long long int)(m)); ++stage) {
    cin >> t0 >> t1;
    t0--;
    t1--;
    for (; t0 != pr[t0]; t0 = num_pr[t0])
      add(1, 1, 0, N, NUM[t0], NUM[t0] + depth[t0] - depth[num_pr[t0]]);
    for (; t1 != pr[t1]; t1 = num_pr[t1])
      add(1, 1, 0, N, NUM[t1], NUM[t1] + depth[t1] - depth[num_pr[t1]]);
    if (t0 != t1) {
      vector<pair<long long int, long long int> > vec;
      for (long long int i = 0;
           i < ((long long int)(((long long int)(E[t0]).size()))); ++i)
        if (depth[E[t0][i]] == 0)
          vec.push_back(make_pair(E[t0][i], loop_num[E[t0][i]]));
      if (dis(t1, t0) < dis(t0, t1)) swap(t0, t1);
      if (dis(t0, t1) == dis(t1, t0)) {
        long long int b0 = 0, b1 = 0;
        if (vec[0].first < vec[1].first) b0 = 1;
        if (vec[0].second == loop_num[t0] - 1 ||
            vec[1].second == loop_num[t0] + 1)
          b1 = 1;
        if ((b0 ^ b1) == 0) swap(t0, t1);
      }
      if (loop_num[t0] < loop_num[t1]) {
        add(1, 1, 0, N, loop_num[t0], loop_num[t1]);
      } else {
        add(1, 1, 0, N, loop_num[t0], loop_end);
        add(1, 1, 0, N, loop_start, loop_num[t1]);
      }
    }
    cout << n - (st[1].num) + ((st[1].loop == loop_end - loop_start) ? 1 : 0)
         << endl;
  }
}
