#include <bits/stdc++.h>
using namespace std;
struct node {
  node *p, *r, *l;
  int size, mysize, on;
  bool flip, edge;
  int id;
  node() {}
  node(int i, int x) {
    id = i;
    size = mysize = x;
    on = x = flip = edge = 0;
    l = r = p = NULL;
  }
  bool is_root() { return !p || (p->l != this && p->r != this); }
  void update() {
    size = mysize;
    on = mysize ? edge : 0;
    if (l) {
      l->relase();
      size += l->size, on += l->on;
    }
    if (r) {
      r->relase();
      size += r->size, on += r->on;
    }
  }
  void relase() {
    if (flip) {
      flip = false;
      on = size - on;
      edge ^= 1;
      if (l) l->flip ^= 1;
      if (r) r->flip ^= 1;
    }
  }
};
void zig(node *p) {
  node *q = p->p, *r = q->p;
  if ((q->l = p->r)) q->l->p = q;
  p->r = q, q->p = p;
  if ((p->p = r)) {
    if (r->l == q) r->l = p;
    if (r->r == q) r->r = p;
  }
  q->update();
}
void zag(node *p) {
  node *q = p->p, *r = q->p;
  if ((q->r = p->l)) q->r->p = q;
  p->l = q, q->p = p;
  if ((p->p = r)) {
    if (r->l == q) r->l = p;
    if (r->r == q) r->r = p;
  }
  q->update();
}
void push_down(node *p) {
  if (!p->is_root()) push_down(p->p);
  p->relase();
}
void splay(node *p) {
  push_down(p);
  while (!p->is_root()) {
    node *q = p->p;
    if (q->is_root()) {
      if (q->l == p)
        zig(p);
      else
        zag(p);
    } else {
      node *r = q->p;
      if (r->l == q)
        if (q->l == p)
          zig(q), zig(p);
        else
          zag(p), zig(p);
      else if (q->l == p)
        zig(p), zag(p);
      else
        zag(q), zag(p);
    }
  }
  p->update();
}
void expose(node *x) {
  node *r = NULL;
  for (node *p = x; p; p = p->p) {
    splay(p);
    p->r = r;
    p->update();
    r = p;
  }
}
vector<int> ady[100005];
stack<int> pila;
int comp[100005];
bool marcas[100005], enciclo[100005];
node *tree[100005], *treeC[100005];
int ciclo[100005], lenC, posCiclo[100005];
void DFS(int v, int p = -1) {
  pila.push(v);
  marcas[v] = true;
  for (int i = ady[v].size() - 1; i >= 0; i--) {
    int u = ady[v][i];
    if (u == p) continue;
    if (!marcas[u])
      DFS(u, v);
    else {
      if (!pila.empty() && pila.top() == v) {
        int x = 0;
        do {
          x = pila.top();
          pila.pop();
          enciclo[x] = true;
          posCiclo[x] = lenC;
          ciclo[lenC++] = x;
        } while (u != x);
      }
    }
  }
  if (!pila.empty() && pila.top() == v) pila.pop();
}
void DFS2(int v, int p = -1) {
  for (int i = ady[v].size() - 1; i >= 0; i--) {
    int u = ady[v][i];
    if (u == p || enciclo[u]) continue;
    comp[u] = comp[v];
    tree[u] = new node(u + 1, 1);
    tree[u]->p = tree[v];
    DFS2(u, v);
  }
}
int change(node *p) {
  expose(p), splay(p);
  int ant = p->on;
  p->flip ^= 1;
  p->relase();
  int now = p->on;
  return now - ant;
}
int edgesOn = 0, edgesCicle = 0;
void solve(int v, int u) {
  edgesOn += change(tree[v]);
  edgesOn += change(tree[u]);
  if (comp[v] == comp[u]) return;
  v = comp[v], u = comp[u];
  int a = posCiclo[v], b = posCiclo[u], left, right;
  if (a < b)
    left = a + lenC - b, right = b - a;
  else
    right = lenC - a + b, left = a - b;
  edgesCicle += change(treeC[a]);
  edgesCicle += change(treeC[b]);
  bool isLeft = left < right;
  if (left == right) {
    int I = ciclo[(a - 1 + lenC) % lenC];
    int D = ciclo[(a + 1) % lenC];
    isLeft = (I < D);
  }
  if (isLeft == false) swap(a, b);
  if (a < b) edgesCicle += change(treeC[lenC - 1]);
}
int main() {
  int n, q, v, u;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &v, &u);
    v--, u--;
    ady[v].push_back(u);
    ady[u].push_back(v);
  }
  DFS(0);
  for (int i = 0; i < lenC; i++) {
    comp[ciclo[i]] = ciclo[i];
    tree[ciclo[i]] = new node(ciclo[i] + 1, 0);
    treeC[i] = new node(ciclo[i] + 1, 1);
    if (i > 0) treeC[i]->p = treeC[i - 1];
    DFS2(ciclo[i]);
  }
  while (q--) {
    scanf("%d%d", &v, &u);
    v--, u--;
    solve(v, u);
    printf("%d\n", n - (edgesOn + edgesCicle) + (edgesCicle == lenC));
  }
  return 0;
}
