#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; int n; vector

g[200020]; int deg[200020]; int ans; void dfs(int x, int p){ for(auto &q:g[x]){ int y=q.first; if(y==p){ continue; } dfs(y, x); if(deg[y]){ deg[y]^=1; deg[x]^=1; q.second=1; ans++; }else{ q.second=-1; } } } void dfs0(int x, int p, int t){ for(auto &q:g[x]){ int y=q.first; if(y==p){ q.second=t; continue; } dfs0(y, x, q.second); } } int r; int mx[200020]; void dfs2(int x, int p){ for(auto q:g[x]){ int y=q.first; if(y==p) continue; dfs2(y, x); mx[x]=max(mx[x], mx[y]+q.second); } } int mx2[200020]; void dfs3(int x, int p){ vector v(g[x].size()+1); for(int i=0; i=0; i--){ int y=g[x][i].first; if(y==p) continue; mx2[y]=max(0, max(v[i], mxr)+g[x][i].second); dfs3(y, x); mxr=max(mxr, mx[y]+g[x][i].second); } } int main() { cin>>n; for(int i=0; i>a>>b; a--; b--; g[a].push_back({b, 0}); g[b].push_back({a, 0}); } for(int i=0; i>c>>d; c--; d--; deg[c]^=1; deg[d]^=1; } dfs(0, -1); dfs0(0, -1, -1); dfs2(0, -1); dfs3(0, -1); int mx0=0; for(int i=0; i