#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
bool isCat[mn], isDog[mn];
int par[mn], dp[2][mn], n;
vector<int> adj[mn];
void dfs (int u, int p) {
par[u] = p;
for (int v : adj[u])
if (v != p) dfs(v, u);
}
void initialize (int _n, vector<int> A, vector<int> B) {
n = _n;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, 1);
}
void clearContrib (int u, int v) {
// cout << "clear-contrib " << u << "\n";
if (par[u] != u) clearContrib(par[u], u);
dp[0][u] -= min(isCat[v] ? INT_MAX : dp[0][v], isDog[v] ? INT_MAX : dp[1][v] + 1);
dp[1][u] -= min(isCat[v] ? INT_MAX : dp[0][v] + 1, isDog[v] ? INT_MAX : dp[1][v]);
}
void addContrib (int u, int v) {
dp[0][u] += min(isCat[v] ? INT_MAX : dp[0][v], isDog[v] ? INT_MAX : dp[1][v] + 1);
dp[1][u] += min(isCat[v] ? INT_MAX : dp[0][v] + 1, isDog[v] ? INT_MAX : dp[1][v]);
if (par[u] != u) addContrib(par[u], u);
}
int solve() { return min(isCat[1] ? INT_MAX : dp[0][1], isDog[1] ? INT_MAX : dp[1][1]); }
int cat (int u) {
if (par[u] != u) clearContrib(par[u], u);
isCat[u] = 1;
if (par[u] != u) addContrib(par[u], u);
return solve();
}
int dog (int u) {
if (par[u] != u) clearContrib(par[u], u);
isDog[u] = 1;
if (par[u] != u) addContrib(par[u], u);
return solve();
}
int neighbor (int u) {
if (par[u] != u) clearContrib(par[u], u);
isCat[u] = isDog[u] = 0;
if (par[u] != u) addContrib(par[u], u);
return solve();
}
#ifdef LOCAL
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> A = {1, 2, 2, 4}, B = {2, 3, 4, 5};
initialize(5, A, B);
cout << cat(3) << " " << dog(5) << "\n";
cout << cat(2) << " " << dog(1) << "\n";
cout << neighbor(2) << "\n";
return 0;
}
#endif
