#pragma GCC optimize("O3") #include using namespace std; using ll=long long; using P=pair; template using V=vector; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); // const ll mod=998244353; const ll mod=1000000007; const vector dy={-1,0,1,0},dx={0,-1,0,1}; struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout< bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } templatevoid debag(const vector &a){cerr<<"debag :";for(auto v:a)cerr<void print(const vector &a){for(auto v:a)cout<>n; V> g(n); for(int i=0;i>a>>b; --a;--b; g[a].emplace_back(b); g[b].emplace_back(a); } V

res(n);//最長,部分木の直径 auto dfs1=[&](auto &&self,int cur,int par)->P{ P val={0,0}; V cp; for(int v:g[cur]){ if(v==par)continue; P tmp=self(self,v,cur); cp.emplace_back(tmp.fi); chmax(val.fi,tmp.fi+1); chmax(val.se,tmp.se); } chmax(val.se,val.fi); if((int)cp.size()>=2){ sort(all(cp),greater()); chmax(val.se,cp[0]+cp[1]+2); }else if((int)cp.size()==1){ chmax(val.se,cp[0]+1); } return res[cur]=val; }; dfs1(dfs1,0,-1); ll ans=res[0].se; auto dfs2=[&](auto &&self,int cur,int par,P val)->void{ if(par!=-1){ chmin(ans,(res[cur].se+1)/2+(val.se+1)/2+1); } multiset tmp,tmp2; for(int v:g[cur]){ if(v==par)continue; tmp.emplace(res[v].fi); tmp2.emplace(res[v].se); } tmp.emplace(val.fi-1); tmp2.emplace(val.se); for(int v:g[cur]){ if(v==par)continue; P nval={0,0}; tmp.erase(tmp.find(res[v].fi)); tmp2.erase(tmp2.find(res[v].se)); if((int)tmp.size()>=2){ auto ite=tmp.end(); ite--;ll v=*ite; ite--;v+=*ite; v+=2; chmax(nval.se,v); } nval.fi=*tmp.rbegin()+2; chmax(nval.se,*tmp2.rbegin()); chmax(nval.se,nval.fi); self(self,v,cur,nval); tmp.emplace(res[v].fi); tmp2.emplace(res[v].se); } }; dfs2(dfs2,0,-1,{0,0}); cout<