#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[100005];
int state[100005];
void dfs(int node, int parent, bool &hasCat, bool &hasDog) {
if (state[node] == 1) hasCat = true;
if (state[node] == 2) hasDog = true;
for (int next : adj[node]) {
if (next != parent) {
dfs(next, node, hasCat, hasDog);
}
}
}
int calculateDanger() {
int danger = 0;
for (int u = 1; u <= n; u++) {
for (int v : adj[u]) {
if (u < v) {
bool catU = false, dogU = false;
dfs(u, v, catU, dogU);
bool catV = false, dogV = false;
dfs(v, u, catV, dogV);
if ((catU && dogV) || (dogU && catV)) {
danger++;
}
}
}
}
return danger;
}
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]);
}
fill(state + 1, state + N + 1, 0);
}
int cat(int v) {
state[v] = 1;
return calculateDanger();
}
int dog(int v) {
state[v] = 2;
return calculateDanger();
}
int neighbor(int v) {
state[v] = 0;
return calculateDanger();
}
