#include <iostream>
#include <vector>
#include <array>
#include "catdog.h"

using namespace std;
using Vec = array<int, 2>;

const int N = 1e5 + 5; 
const Vec Evec = {0, 0};

int n, a[N];
vector<int> e[N];
int fa[N], siz[N], dep[N], wson[N];
int dfn[N], rmp[N], now, tp[N], bot[N];
int f[N][2], g[N][2];

void Dfs (int u) {
  siz[u] = 1;
  dep[u] = dep[fa[u]] + 1;
  for (auto v : e[u]) {
    if (v != fa[u]) {
      fa[v] = u, Dfs(v);
      siz[u] += siz[v];
      if (siz[v] > siz[wson[u]]) {
        wson[u] = v;
      }
    }
  }
}

void Dfs2 (int u, int t) {
  dfn[u] = ++now;
  rmp[now] = u; 
  tp[u] = t, bot[t] = u; 
  if (wson[u]) {
    Dfs2(wson[u], t);
  }
  for (auto v : e[u]) {
    if (v != fa[u] && v != wson[u]) {
      Dfs2(v, v);
    }
  }
}

struct Mat {
  array<Vec, 2> a;

  Vec& operator[] (int x) {
    return a[x];
  }

  Mat () { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; }
  Mat (int p, int q, int r, int s) {
    a[0][0] = p, a[0][1] = q, a[1][0] = r, a[1][1] = s;
  }

  Mat operator* (Mat b) {
    Mat res(N, N, N, N);
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
        }
      }
    }
    return res;
  }

  Vec operator* (Vec b) {
    Vec res = {N, N};
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        res[i] = min(res[i], a[i][j] + b[j]);
      }
    }
    return res;
  }
} mat[N];

namespace Seg {
  #define lc (k << 1)
  #define rc ((k << 1) | 1)
  const int T = N * 4;

  Mat tr[T];

  void Pushup (int k) {
    tr[k] = tr[lc] * tr[rc];
  }

  void Update (int k, int x, Mat a, int L = 1, int R = n) {
    if (L == R){ 
      tr[k] = a;
      return;
    }
    int mid = (L + R) >> 1;
    if (x <= mid) {
      Update(lc, x, a, L, mid);
    }
    else {
      Update(rc, x, a, mid + 1, R);
    }
    Pushup(k);
  }

  Mat Query (int k, int l, int r, int L = 1, int R = n) {
    if (l <= L && r >= R) {
      return tr[k];
    }
    int mid = (L + R) >> 1;
    if (l > mid) { 
      return Query(rc, l, r, mid + 1, R);
    } 
    else if (r <= mid) {
      return Query(lc, l, r, L, mid);
    }
    else { 
      return Query(lc, l, r, L, mid) * Query(rc, l, r, mid + 1, R);
    }
  }

  #undef lc 
  #undef rc
}

void Calc (int u) {
  Mat ret = Seg::Query(1, dfn[u], dfn[bot[u]]);
  Vec rev = ret * Evec;
  f[u][0] = rev[0], f[u][1] = rev[1];
} 

void Build_mat (int u) {
  int d0 = (a[u] == 1 ? N : 0), d1 = (a[u] == 2 ? N : 0);
  mat[u] = Mat(g[u][0] + d0, g[u][0] + 1 + d0, g[u][1] + 1 + d1, g[u][1] + d1);
  Seg::Update(1, dfn[u], mat[u]);
}

void DP (int u) {
  for (auto v : e[u]) {
    if (v != fa[u] && v != wson[u]) {
      DP(v);
      g[u][0] += min(f[v][0], f[v][1] + 1);
      g[u][1] += min(f[v][1], f[v][0] + 1);
    }
  }
  if (wson[u]) { 
    DP(wson[u]);
  }
  Build_mat(u);
  if (tp[u] == u) {
    Calc(u);
  }
}

void Update_path (int u) {
  while (u) {
    Build_mat(u);
    int v = tp[u], tf[2] = {f[v][0], f[v][1]};
    Calc(v);
    u = fa[v];
    if (u) {
      g[u][0] += min(f[v][0], f[v][1] + 1) - min(tf[0], tf[1] + 1);
      g[u][1] += min(f[v][1], f[v][0] + 1) - min(tf[1], tf[0] + 1);
    }
  }
}

void initialize (int N, vector<int> A, vector<int> B) {
  n = N;
  for (int i = 0; i < n; ++i) {
    e[A[i]].push_back(B[i]);
    e[B[i]].push_back(A[i]);
  }
  Dfs(1), Dfs2(1, 1), DP(1);
}

int Get_ans () {
  return min(f[1][0], f[1][1]);
}

int cat (int v) {
  a[v] = 1, Update_path(v);
  return Get_ans();
}

int dog (int v) {
  a[v] = 2, Update_path(v);
  return Get_ans();
}

int neighbor (int v) {
  a[v] = 0, Update_path(v);
  return Get_ans();
}

// void Test () {
//   int N;
//   cin >> N;
//   vector<int> A(N), B(N);
//   for (int i = 0; i < N - 1; ++i) {
//     cin >> A[i] >> B[i];
//   }
//   initialize(N, A, B);
//   int Q;
//   cin >> Q;
//   for (int T, v; Q--; ) {
//     cin >> T >> v;
//     cout << (T == 1 ? cat : (T == 2 ? dog : neighbor))(v) << '\n';
//   }
// }

// int main () { Test(); }