// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int n, sz[N], par[N], chain[N], pos[N], len[N], state[N];
vector<int> G[N];
struct Node {
int s[2][2];
Node(int a = inf, int b = inf, int c = inf, int d = inf) {
s[0][0] = a; s[0][1] = b;
s[1][0] = c; s[1][1] = d;
}
friend Node combine(const Node &L, const Node &R) {
Node res;
REP(i, 2) REP(j, 2) if (L.s[i][j] != inf)
REP(x, 2) REP(y, 2) if (R.s[x][y] != inf)
minimize(res.s[i][y], L.s[i][j] + R.s[x][y] + (j != x));
return res;
}
};
struct SegmentTree {
vector<Node> node;
int sz;
SegmentTree(int n = 0):
sz(n), node(4 * n + 5) {}
void update(int pos, Node val) {
int id = 1, l = 1, r = sz;
while(l < r) {
int mid = (l + r) >> 1;
if (pos > mid) id = (id << 1 | 1), l = mid + 1;
else id = (id << 1), r = mid;
}
node[id] = val;
while(id) {
id >>= 1;
node[id] = combine(node[id << 1], node[id << 1 | 1]);
}
}
int get_ans() {
return min({node[1].s[0][0], node[1].s[1][1], node[1].s[0][1], node[1].s[1][0]});
}
} it[N];
Node base[3] = {Node(0, inf, inf, 0), Node(0, inf, inf, inf), Node(inf, inf, inf, 0)};
void dfs(int u, bool create_chain, bool is_head) {
sz[u] = 1;
for(int v : G[u]) if (v != par[u]) {
par[v] = u;
dfs(v, false, false);
sz[u] += sz[v];
}
if (create_chain == false) return;
chain[u] = (is_head ? u : chain[par[u]]);
pos[u] = ++len[chain[u]];
sort(all(G[u]), [&](int &x, int &y){
return sz[x] > sz[y];
});
int heavy = (u == 1 ? G[u][0] : G[u][1]);
for(int v : G[u]) if (v != par[u])
dfs(v, true, (v != heavy));
}
int sum_child[2][N];
void update(int u) {
while(u > 0) {
int head = chain[u];
Node cur = it[head].node[1];
// del
sum_child[0][par[head]] -= min({cur.s[0][0], cur.s[0][1], cur.s[1][0] + 1, cur.s[1][1] + 1});
sum_child[1][par[head]] -= min({cur.s[1][0], cur.s[1][1], cur.s[0][0] + 1, cur.s[0][1] + 1});
// recalc
cur = base[state[u]];
if (cur.s[0][0] != inf) cur.s[0][0] += sum_child[0][u];
if (cur.s[1][1] != inf) cur.s[1][1] += sum_child[1][u];
it[head].update(pos[u], cur);
// add
cur = it[head].node[1];
sum_child[0][par[head]] += min({cur.s[0][0], cur.s[0][1], cur.s[1][0] + 1, cur.s[1][1] + 1});
sum_child[1][par[head]] += min({cur.s[1][0], cur.s[1][1], cur.s[0][0] + 1, cur.s[0][1] + 1});
u = par[head];
}
}
int cat(int v) {state[v] = 1; update(v); return it[1].get_ans();}
int dog(int v) {state[v] = 2; update(v); return it[1].get_ans();}
int neighbor(int v) {state[v] = 0; update(v); return it[1].get_ans();}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
REP(i, (int)A.size()) {
G[A[i]].pb(B[i]);
G[B[i]].pb(A[i]);
}
dfs(1, true, true);
FOR(i, 1, n) if (i == chain[i])
it[i] = SegmentTree(len[i]);
FOR(i, 1, n) it[chain[i]].update(pos[i], base[0]);
}
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (fopen(task".inp", "r")) {
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
// }
// initialize(5, {1, 2, 2, 4}, {2, 3, 4, 5});
// cout << cat(3) << ' ' << dog(5) << '\n';
// cout << cat(2) << ' ' << dog(1) << '\n';
// cout << neighbor(2) << '\n';
// return 0;
// }
