#include "catdog.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
#include <vector>
#include <stdlib.h>
#define INF 100000005
using namespace std;
int x,cats[200005],dogs[200005],tata[200005],niv[200005],nr,valoare[200005];
vector <int> gr[200005];
void dfs(int x,int t,int nivel)
{
tata[x]=t;
niv[x]=nivel;
for (int i=0; i<gr[x].size(); i++)
{
int nod=gr[x][i];
if (nod!=t)
{
dfs(nod,x,nivel+1);
}
}
}
int n2;
void initialize(int n, std::vector<int> A, std::vector<int> B)
{
n2=n;
int i;
for (i=0; i<n-1; i++)
{
gr[A[i]].push_back(B[i]);
gr[B[i]].push_back(A[i]);
}
for (i=1; i<=n; i++)
{
cats[i]=0;
dogs[i]=0;
}
nr=0;
dfs(1,0,1);
}
void solve(int x,int t)
{
for (int i=0;i<gr[x].size();i++)
{
int nod=gr[x][i];
if (nod!=t)
{
solve(nod,x);
}
}
if (valoare[x]==1)
{
dogs[x]=INF;
}
else
if (valoare[x]==2)
{
cats[x]=INF;
}
int i;
for (i=0;i<gr[x].size();i++)
{
int nod=gr[x][i];
if (nod!=t)
{
dogs[x]+=min(dogs[nod],cats[nod]+1);
cats[x]+=min(cats[nod],dogs[nod]+1);
}
}
}
int calculeaza()
{
int i;
for (i=1;i<=n2;i++)
{
cats[i]=dogs[i]=0;
}
solve(1,0);
if (valoare[1]==1)
{
return cats[1];
}
if (valoare[1]==2)
{
return dogs[1];
}
return min(dogs[1],cats[1]);
}
int cat(int v)
{
valoare[v]=1;
return calculeaza();
}
int dog(int v)
{
valoare[v]=2;
return calculeaza();
}
int neighbor(int v)
{
valoare[v]=0;
return calculeaza();
}
/*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;
}*/
