#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100050;
int inc[MaxN], vst[MaxN], n, in[MaxN], ax[MaxN], N, st[MaxN], ST;
int pos[MaxN], Fa[MaxN], m, tot;
struct Edge {
  int v;
  Edge *nxt;
} buf[MaxN * 2], *g[MaxN], *pt;
void add(int u, int v) {
  pt->v = v;
  pt->nxt = g[u];
  g[u] = pt++;
}
void dfs(int u, int zu) {
  if (inc[u]) {
    ax[N] = u;
    pos[u] = N++;
    zu = u;
  }
  st[u] = zu;
  for (Edge *now = g[u]; now; now = now->nxt) {
    int v = now->v;
    if (st[v] != -1) continue;
    if (!inc[v]) Fa[v] = u;
    dfs(v, zu);
  }
}
struct Link_Cut_Tree {
  struct Node {
    int sz, s0, key, rev;
    Node *fa, *c[2];
  } buf[MaxN], *nil, *pos[MaxN], *stk[MaxN];
  Node *NewNode(int k) {
    Node *x = pos[k];
    x->fa = pos[Fa[k]];
    x->c[0] = x->c[1] = nil;
    x->key = 1;
    x->rev = 0;
    x->sz = x->s0 = 1;
    return x;
  }
  void init() {
    nil = buf;
    nil->key = nil->rev = 0;
    nil->s0 = nil->sz = 0;
    nil->fa = nil->c[0] = nil->c[1] = nil;
    pos[0] = nil;
    for (int i = 1; i <= n; i++) pos[i] = buf + i;
    for (int i = 1; i <= n; i++) NewNode(i);
  }
  void Rev(Node *x) {
    if (x == nil) return;
    x->rev ^= 1;
    x->key ^= 1;
    x->s0 = x->sz - x->s0;
  }
  void Down(Node *x) {
    if (x->rev) Rev(x->c[0]), Rev(x->c[1]), x->rev = 0;
  }
  void Up(Node *x) {
    x->sz = x->c[0]->sz + 1 + x->c[1]->sz;
    x->s0 = x->c[0]->s0 + x->key + x->c[1]->s0;
  }
  bool isRoot(Node *x) {
    if (x->fa == nil || (x->fa->c[0] != x && x->fa->c[1] != x)) return 1;
    return 0;
  }
  void Rotate(Node *x, int f) {
    Node *y = x->fa;
    Down(y), Down(x);
    y->c[f ^ 1] = x->c[f];
    if (x->c[f] != nil) x->c[f]->fa = y;
    x->fa = y->fa;
    if (y->fa != nil) {
      if (y->fa->c[0] == y)
        y->fa->c[0] = x;
      else if (y->fa->c[1] == y)
        y->fa->c[1] = x;
    }
    y->fa = x;
    x->c[f] = y;
    Up(y);
  }
  void Splay(Node *x) {
    int Cnt = 0;
    Node *t = x;
    while (!isRoot(t)) stk[Cnt++] = t->fa, t = t->fa;
    for (int i = Cnt - 1; i >= 0; i--) Down(stk[i]);
    for (Down(x); !isRoot(x);) {
      if (isRoot(x->fa)) {
        if (x->fa->c[0] == x)
          Rotate(x, 1);
        else
          Rotate(x, 0);
      } else {
        Node *y = x->fa, *z = y->fa;
        if (z->c[0] == y) {
          if (y->c[0] == x)
            Rotate(y, 1), Rotate(x, 1);
          else
            Rotate(x, 0), Rotate(x, 1);
        } else {
          if (y->c[1] == x)
            Rotate(y, 0), Rotate(x, 0);
          else
            Rotate(x, 1), Rotate(x, 0);
        }
      }
    }
    Up(x);
  }
  Node *Access(int k) {
    Node *x = pos[k], *pre = nil;
    for (; x != nil; x = x->fa) {
      Splay(x);
      x->c[1] = pre;
      Up(pre = x);
    }
    return pre;
  }
  void LCA(int x, int y) {
    if (x == y) return;
    Access(x);
    for (Node *u = pos[y], *v = nil; u != nil; u = u->fa) {
      Splay(u);
      if (u->fa == nil) {
        tot += u->c[1]->sz - 2 * u->c[1]->s0;
        tot += v->sz - 2 * v->s0;
        Rev(u->c[1]);
        Up(u);
        Rev(v);
        return;
      }
      u->c[1] = v;
      Up(u);
      v = u;
    }
  }
} lct;
struct SEG_TREE {
  int sum[MaxN], s0[MaxN], rev[MaxN], N;
  void build(int k, int L, int R) {
    rev[k] = 0;
    sum[k] = s0[k] = R - L + 1;
    if (L == R) return;
    int mid = (L + R) / 2;
    build(k * 2, L, mid);
    build(k * 2 + 1, mid + 1, R);
  }
  void Rev(int k) {
    rev[k] ^= 1;
    s0[k] = sum[k] - s0[k];
  }
  void Down(int k) {
    Rev(k * 2), Rev(k * 2 + 1);
    rev[k] = 0;
  }
  void Up(int k) { s0[k] = s0[k * 2] + s0[k * 2 + 1]; }
  void update(int k, int L, int R, int l, int r) {
    if (l > r) return;
    if (l <= L && R <= r) {
      Rev(k);
      return;
    }
    if (rev[k]) Down(k);
    int mid = (L + R) / 2;
    if (l <= mid) update(k * 2, L, mid, l, r);
    if (r > mid) update(k * 2 + 1, mid + 1, R, l, r);
    Up(k);
  }
} seg;
void sol(int x, int y) {
  int sx = st[x];
  int sy = st[y];
  int ret = 0;
  if (sx != sy) {
    int xx = min(pos[sx], pos[sy]), yy = max(pos[sx], pos[sy]);
    int aa, bb;
    if (pos[sx] < pos[sy])
      aa = ax[(xx + 1) % N], bb = ax[(xx - 1 + N) % N];
    else
      bb = ax[(yy + 1) % N], aa = ax[(yy - 1 + N) % N];
    if (yy - xx < N - (yy - xx) || (yy - xx == N - (yy - xx) && aa < bb))
      seg.update(1, 0, N - 1, xx + 1, yy);
    else {
      if (yy + 1 <= N - 1) seg.update(1, 0, N - 1, yy + 1, N - 1);
      seg.update(1, 0, N - 1, 0, xx);
    }
    lct.LCA(sx, x);
    lct.LCA(sy, y);
  } else
    lct.LCA(x, y);
  ret = tot + max(seg.s0[1], 1);
  printf("%d\n", ret);
}
int main() {
  pt = buf;
  memset(g, 0, sizeof(g));
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
    in[x]++;
    in[y]++;
  }
  N = 0;
  for (int i = 1; i <= n; i++) {
    if (in[i] == 1)
      ax[N++] = i, inc[i] = 0;
    else
      inc[i] = 1;
  }
  for (int i = 0; i < N; i++) {
    int u = ax[i];
    for (Edge *now = g[u]; now; now = now->nxt)
      if ((--in[now->v]) == 1) ax[N++] = now->v, inc[now->v] = 0;
  }
  memset(st, -1, sizeof(st));
  memset(Fa, 0, sizeof(Fa));
  N = 0;
  for (int i = 1; i <= n; i++)
    if (inc[i]) {
      ST = i;
      dfs(i, 0);
      break;
    }
  lct.init();
  seg.N = N;
  seg.build(1, 0, N - 1);
  tot = n - N;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    sol(x, y);
  }
  return 0;
}
