#include <bits/stdc++.h>
using namespace std;
const long long N = 3e5 + 101;
const long long M = 1e6 + 101;
const long long big = 1e16;
const long long hsh2 = 1964325029;
const long long mod = 1e9 + 7;
const long double EPS = 1e-15;
const long long block = 1e7;
const long long shift = 2e3;
long long n, m;
vector<long long> g[N];
bool was[N];
long long prc[N];
vector<long long> ccl;
long long fnd = 0;
bool used[N];
void cycle(long long v, long long p) {
  was[v] = 1;
  for (auto u : g[v]) {
    if (u == p) continue;
    if (fnd) continue;
    if (was[u]) {
      prc[u] = v;
      fnd = u;
    } else if (!fnd)
      prc[u] = v, cycle(u, v);
  }
}
long long H, clr[N], sz[N], bp[N][20], tin[N], tout[N], hpr[N];
long long prt[N];
struct seg {
  long long t[4 * N] = {0}, u[4 * N] = {0};
  void push(long long v, long long l, long long r) {
    if (u[v]) {
      t[v] = r - l + 1 - t[v];
      u[v * 2] ^= u[v];
      u[v * 2 + 1] ^= u[v];
      u[v] = 0;
    }
  }
  void upd(long long l, long long r, long long v = 1, long long tl = 1,
           long long tr = n) {
    push(v, tl, tr);
    if (l > tr || tl > r) return;
    if (l <= tl && tr <= r) return (void)(u[v] = 1, push(v, tl, tr));
    long long m = (tl + tr) >> 1;
    upd(l, r, v * 2, tl, m);
    upd(l, r, v * 2 + 1, m + 1, tr);
    t[v] = t[v * 2] + t[v * 2 + 1];
  }
} rt, rt2;
void clrdfs(long long v, long long p, long long pr) {
  clr[v] = pr;
  sz[v] = 1;
  bp[v][0] = p;
  for (auto u : g[v])
    if (!clr[u] && u != p) clrdfs(u, v, pr), sz[v] += sz[u];
}
void hld(long long v, long long p, long long pr) {
  hpr[v] = pr;
  tin[v] = ++tout[0];
  for (auto u : g[v])
    if (u != p && !prt[u] && sz[u] * 2 > sz[v]) hld(u, v, pr);
  for (auto u : g[v])
    if (u != p && !prt[u] && sz[u] * 2 <= sz[v]) hld(u, v, u);
  tout[v] = tout[0];
}
bool upper(long long a, long long b) {
  return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
void Decompose() {
  cycle(1, 0);
  long long st = prc[fnd];
  ccl.push_back(fnd);
  while (st != fnd) ccl.push_back(st), st = prc[st];
  long long it = 0;
  for (auto u : ccl) prt[u] = ++it, clr[u] = u;
  for (auto u : ccl) clrdfs(u, 0, u), hld(u, 0, u);
}
void upd(long long a, long long b) {
  long long first = 0;
  while (1) {
    long long z = hpr[a];
    if (upper(z, b)) z = b;
    rt.upd(tin[z], tin[a]);
    if (z == b) break;
    a = bp[z][0];
  }
  rt.upd(tin[b], tin[b]);
}
void supd(long long a, long long b) {
  if (a == b) return;
  a = prt[a] - 1, b = prt[b] - 1;
  long long L = (a - 1 + ccl.size()) % (long long)(ccl.size());
  long long R = (a + 1) % (long long)(ccl.size());
  long long rst = abs(b - a);
  long long rst2 = ccl.size() - rst;
  if (rst != rst2) {
    if (rst < rst2)
      rt2.upd(min(a, b) + 1, max(a, b));
    else
      rt2.upd(max(a, b) + 1, ccl.size()), rt2.upd(1, min(a, b));
    return;
  }
  if (ccl[L] < ccl[R]) swap(a, b);
  if (a < b) {
    rt2.upd(a + 1, b);
  } else {
    rt2.upd(a + 1, ccl.size());
    rt2.upd(1, b);
  }
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1, a, b; i <= n; i++) {
    cin >> a >> b;
    g[a].push_back(b), g[b].push_back(a);
  }
  Decompose();
  while (m--) {
    long long a, b;
    cin >> a >> b;
    upd(a, clr[a]);
    upd(b, clr[b]);
    supd(clr[a], clr[b]);
    long long ans = (n - ccl.size()) - rt.t[1];
    ans += max(1ll, (long long)(ccl.size() - rt2.t[1]));
    cout << ans << '\n';
  }
}
