#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
void setmin(int &x, int y) {
x = min(x, y);
}
const int maxn = 2e5+10;
const int inf = 1e7;
struct dsu0 {
vector<int> par, siz;
int n;
int cc;
int largest;
void init(int n) {
assert(n>0);
this->n=n;
cc=n;
par.resize(n+10);siz.resize(n+10);
for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
largest=1;
}
int parent(int x) {
assert(x>=0 && x<n);
return par[x]==x?x:par[x]=parent(par[x]);
}
bool join(int x, int y) {
x=parent(x);y=parent(y);
if (x==y) return false;
cc--;
if (siz[x]<siz[y]) swap(x,y);
siz[x]+=siz[y];par[y]=x;
largest=max(largest,siz[x]);
return true;
}
};
const int NONE = 1;
const int CAT = 2;
const int DOG = 3;
int n;
vector<int> g[maxn];
vector<pair<int,int>> edges;
int state[maxn];
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i=0; i<n-1; i++) {
int u = A[i];
int v = B[i];
u--; v--;
assert(u>=0 && v>=0); // assume given to us 1-indexed
assert(u<n && v<n);
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({u,v});
}
for (int i=0; i<n; i++) {
state[i] = NONE;
}
}
void print() {
return;
for (int i=0; i<n; i++) {
cout<<state[i]<<" ";
}
cout<<endl;
}
int brute() {
int res = n+10;
for (int mask=0; mask<(1<<(n-1)); mask++) {
dsu0 dsu;
dsu.init(n);
for (int j=0; j<n-1; j++) {
if (!(mask>>j&1)) {
int u = edges[j].first;
int v = edges[j].second;
dsu.join(u, v);
}
}
map<int,int> mp;
bool ok = true;
for (int i=0; i<n && ok; i++) {
int cc = dsu.parent(i);
if (state[i] == NONE) continue;
if (!mp.count(cc)) {
mp[cc] = state[i];
}
if (mp[cc] != state[i]) {
ok = false;
}
}
if (ok) {
int rm = __builtin_popcount(mask);
res = min(res, rm);
}
}
return res;
}
int dp[maxn][4];
void dfs(int at, int p) {
if (state[at] == NONE) {
dp[at][NONE] = 0;
dp[at][CAT] = 0;
dp[at][DOG] = 0;
} else {
dp[at][NONE] = inf;
dp[at][CAT] = inf;
dp[at][DOG] = inf;
dp[at][state[at]] = 0;
}
for (int to: g[at]) {
if (to == p) {
continue;
}
dfs(to, at);
if (state[at] == NONE) {
dp[at][NONE] += min({dp[to][NONE], 1+dp[to][CAT], 1+dp[to][DOG]});
dp[at][CAT] += min({dp[to][NONE], dp[to][CAT], 1+dp[to][DOG]});
dp[at][DOG] += min({dp[to][NONE], 1+dp[to][CAT], dp[to][DOG]});
} else {
int cur = state[at];
int other = cur^CAT^DOG;
dp[at][state[at]] += min({dp[to][NONE], dp[to][cur], 1+dp[to][other]});
}
}
}
int solve() {
for (int i=0; i<=n+2; i++) {
for (int j=0; j<4; j++) {
dp[i][j] = inf;
}
}
dfs(0, -1);
int res = min({dp[0][NONE], dp[0][CAT], dp[0][DOG]});
assert(res < inf);
return res;
}
int cat(int v) {
v--;
state[v] = CAT;
print();
return solve();
}
int dog(int v) {
v--;
state[v] = DOG;
print();
return solve();
}
int neighbor(int v) {
v--;
state[v] = NONE;
print();
return solve();
}
