#include<bits/stdc++.h>
#include "catdog.h"
#define ll long long
using namespace std;
const int inf=1e9;
int min(int a,int b)
{
if (a<b)
return a;
return b;
}
struct mat
{
int a[2][2];
void init()
{
a[0][0]=a[1][1]=0;
a[1][0]=a[0][1]=inf;
}
mat()
{
init();
}
mat operator * (mat b) const
{
mat c;
int i,j,k,e;
for(i=0;i<2;i++)
for(j=0;j<2;j++){
c.a[i][j]=inf;
for(k=0;k<2;k++)
for(e=0;e<2;e++)
c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[e][j]+(k^e));
}
return c;
}
}aint[200005];
int l[200005],r[200005],root[100005],u;
void update(int &nod,int st,int dr,int poz,int a,int b)
{
if (nod==0)
nod=++u;
if (st==dr){
aint[nod].a[0][0]+=a;
aint[nod].a[1][1]+=b;
return ;
}
int mij=(st+dr)/2;
if (poz<=mij)
update(l[nod],st,mij,poz,a,b);
else
update(r[nod],mij+1,dr,poz,a,b);
aint[nod]=aint[l[nod]]*aint[r[nod]];
}
pair<int,int> query(int nod)
{
int a=min(aint[nod].a[0][0],aint[nod].a[0][1]),b=min(aint[nod].a[1][0],aint[nod].a[1][1]);
a=min(a,b+1);
b=min(b,a+1);
return make_pair(a,b);
}
int head[100005],sz[100005],dep[100005],t[100005],sz2[100005];
vector<int>g[100005];
void dfs(int nod,int tat)
{
t[nod]=tat;
dep[nod]=dep[tat]+1;
sz[nod]=1;
for(auto it:g[nod])
if (it!=tat)
dfs(it,nod),sz[nod]+=sz[it];
}
void hld(int nod,int tat)
{
if (head[nod]==0)
head[nod]=nod;
sz2[head[nod]]++;
int ok=0;
for(auto it:g[nod])
if (it!=tat && sz[ok]<sz[it])
ok=it;
if (ok)
head[ok]=head[nod];
for(auto it:g[nod])
if (it!=tat)
hld(it,nod);
}
int nr[100005];
void initialize(int n,vector<int>a,vector<int>b)
{
int i;
for(i=0;i<n-1;i++)
g[a[i]].push_back(b[i]),g[b[i]].push_back(a[i]);
dfs(1,0);
hld(1,0);
}
int calc()
{
pair<int,int>aux=query(root[1]);
return min(aux.first,aux.second);
}
void mark(int nod,int a,int b)
{
while(nod){
int xa,xb,ya,yb;
pair<int,int>aux=query(root[head[nod]]);
xa=aux.first;
xb=aux.second;
update(root[head[nod]],1,sz2[head[nod]],dep[nod]-dep[head[nod]]+1,a,b);
aux=query(root[head[nod]]);
ya=aux.first;
yb=aux.second;
a=ya-xa;
b=yb-xb;
nod=t[head[nod]];
}
}
int cat(int nod)
{
nr[nod]=1;
mark(nod,100000,0);
return calc();
}
int dog(int nod)
{
nr[nod]=2;
mark(nod,0,100000);
return calc();
}
int neighbor(int nod)
{
if (nr[nod]==1)
mark(nod,-100000,0);
if (nr[nod]==2)
mark(nod,0,-100000);
return calc();
}
