#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
const int BIG = 1e9 + 10;
int x;
vector<vector<int>> tree;
vector<int> type;
int n;
vector<int> dfs(int v, int pr = -1)
{
vector<int> cur(3);
for (int tov : tree[v])
if (tov != pr)
{
vector<int> res = dfs(tov, v);
for (int f = 0; f < 3; ++f)
{
int mn = n;
for (int tof = 0; tof < 3; ++tof)
if (tof != f)
{
mn = min(mn, res[tof]);
}
cur[f] += min(res[f], mn + 1);
}
}
if (type[v])
cur[1 + (2 - type[v])] = cur[0] = n;
cur[0] = min(cur[0], n);
cur[1] = min(cur[1], n);
cur[2] = min(cur[2], n);
return cur;
}
int getAns()
{
auto getCur = dfs(0);
return min({getCur[0], getCur[1], getCur[2]});
}
void initialize(int N, std::vector<int> A, std::vector<int> B)
{
n = N;
tree.resize(n);
type.resize(n, 0);
for (int i = 0; i < n - 1; ++i)
{
--A[i], --B[i];
tree[A[i]].pb(B[i]);
tree[B[i]].pb(A[i]);
}
}
int cat(int v)
{
--v;
type[v] = 1;
return getAns();
}
int dog(int v)
{
--v;
type[v] = 2;
return getAns();
}
int neighbor(int v)
{
--v;
type[v] = 3;
return getAns();
}
// #include "catdog.h"
// #include <cstdio>
// #include <cassert>
// #include <vector>
// #include <stdlib.h>
// int readInt()
// {
// int i;
// if (scanf("%d", &i) != 1)
// {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return i;
// }
// int main()
// {
// int N = readInt();
// std::vector<int> A(N - 1), B(N - 1);
// for (int i = 0; i < N - 1; i++)
// {
// A[i] = readInt();
// B[i] = readInt();
// }
// int Q;
// assert(scanf("%d", &Q) == 1);
// std::vector<int> T(Q), V(Q);
// for (int i = 0; i < Q; i++)
// {
// T[i] = readInt();
// V[i] = readInt();
// }
// initialize(N, A, B);
// std::vector<int> res(Q);
// for (int j = 0; j < Q; j++)
// {
// if (T[j] == 1)
// res[j] = cat(V[j]);
// else if (T[j] == 2)
// res[j] = dog(V[j]);
// else
// res[j] = neighbor(V[j]);
// }
// for (int j = 0; j < Q; j++)
// printf("%d\n", res[j]);
// return 0;
// }
